Showing posts with label Codeforces. Show all posts
Showing posts with label Codeforces. Show all posts
2015 ACM Amman Collegiate Programming Contest ( H.Bridge)
Consider each component as a single vertex and add the bridges again, now you have a tree where all edges are bridges (in the original graph).
Number of single cycle components in an undirected graph (CF-977E)
E. Cyclic Components
resource
হিন্টঃ প্রতিটি কম্পোনেন্ট এ চেক করবো তাদের প্রত্যেকটি নোডের ডিগ্রি দুই কিনা, যদি দুই হয় তাইলে সেটা একটা সিঙ্গেল সাইকেল কম্পোনেন্ট।
F1. Tree Cutting (Easy Version
F1. Tree Cutting (Easy Version)
Topic: DFS
Concept: প্রতিটা প্যারেন্ট এর চাইল্ড কোন কোন কালার আছে তার হিসাব রাখবো, যেমন প্রথম উদাহরনে -
১ নং নোডের চাইল্ড এর সংখ্যা হবে ১টা লাল, ২টা নীল , ১টা নরমাল।
২ নং নোডের চাইল্ড এর সংখ্যা হবে ১টা লাল, ১টা নীল , ২টা নরমাল।
৩ নং এর ১টা নরমাল (নিজের কালার)।
৪ নং নোডের চাইল্ড এর সংখ্যা হবে ১টা লাল ( এইটা বাদ দিয়ে এন্সার পাব)।
৫ নং নোডের চাইল্ড এর সংখ্যা হবে 1টা নীল।
Solution 01:
B. F1 Champions
B. F1 Champions
operatopr overloading conecpt
Solution 01: help from rng_58
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 | #include<bits/stdc++.h> using namespace std; #define INF 1<<30 #define MAX 10005 #define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0); int p[] = {25, 18, 15, 12, 10, 8, 6, 4, 2, 1}; map <string, int> mp; string name[1010]; int a[1000][1000], point[1000]; vector<pair<string, int> > v; bool cmp1(int x, int y) { if(point[x] != point[y]) return (point[x] > point[y]); if(a[x][0] != a[y][0]) return (a[x][0] > a[y][0]); for(int i = 0; i < 100; i++) if(a[x][i] != a[y][i]) return a[x][i] > a[y][i]; return true; } bool cmp2(int x, int y) { if(a[x][0] != a[y][0]) return (a[x][0] > a[y][0]); if(point[x] != point[y]) return (point[x] > point[y]); for(int i = 0; i < 100; i++) if(a[x][i] != a[y][i]) return a[x][i] > a[y][i]; return true; } int main() { FASTIO ///* //double start_time = clock(); #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); freopen("error.txt", "w", stderr); #endif //*/ int T; cin >> T; while(T--){ int n; cin >> n; for(int i = 0; i < n; i++){ string s; cin >> s; v.push_back({s,i}); // string + position } } int N = 0; for(int i = 0; i < v.size(); i++){ mp[v[i].first] = 0; // cerr<<v[i].first << " "<<v[i].second << endl; } for(auto it = mp.begin(); it != mp.end(); it++){ // cerr << it->first << " "<<it->second << endl; name[N] = it->first; it->second = N; N++; // cerr << it->first << " "<<it->second << endl; //cerr << name[N-1]<< "\n"; } for(int i = 0; i < v.size(); i++){ int player = mp[v[i].first]; int rank = v[i].second; a[player][rank]++; if(rank < 10) point[player] += p[rank]; } /*for(int i =0; i < 10; i++){ for(int j = 0; j < 10; j ++){ cerr << setw(2) << a[i][j]; } cerr << endl; }*/ int cnt = 0, cnt2 = 0; for(int i =0; i < N; i++){ if(cmp1(i,cnt)) cnt = i; if(cmp2(i, cnt2)) cnt2 = i; } cout << name[cnt] << "\n" << name[cnt2] << "\n"; //double end_time = clock(); //printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000); return 0; } |