#include <bits/stdc++.h> using namespace std; #define ll long long #define F first #define S second #define mp make_pair #define pii pair<int,int> #define vi vector<int> #define pq priority_queue #define pb push_back #define watch(x) cout << (#x) << " is " << (x) << endl #define ALL(a) (a.begin()),(a.end()) #define FOR(x,to) for(x=0;x<(to);x++) #define FORI(a,b) for(int i = a; i<b; i++) #define fastio ios::sync_with_stdio(0); cin.tie(NULL); const int INF = 0x3f3f3f3f; struct ar{ ll x,y; }; ar v[100100]; int p[100100] = {0}; ll id[100100]; ll sz[100100]; ll num; ll find(ll x){ if(id[x] == x) return x; return id[x] = find(id[x]); } void join(ll x, ll y){ ll p = find(x); ll q = find(y); if(p==q) return; num; if(sz[p] > sz[q]) { ll t = q; p = q; q = t; } id[p] = q; sz[p] += sz[q]; } int main(){ fastio ll n,m,i,q; cin >> n >> m; num = n; ll arf[100100]; ll ans[100100];
FOR(i,m){ cin >> v[i+1].x >> v[i+1].y; } FOR(i,m+1){ id[i+1] = i+1; sz[i+1] = 1; } cin >> q; FOR(i,q){ ll x; cin >> x; p[x] = 1; arf[qi] = x; } FOR(i,m+1){ if(i==0) continue; if(!p[i]){ join(v[i].x, v[i].y); } }
ans[q] = num; for(int i = 1; i<=q; i++){ join(v[arf[i]].x, v[arf[i]].y);
ans[qi] = num;
}
for(int i = 1; i<=q; i++){ cout << ans[i] << " "; }
cout << "\n"; return 0; }
Edited by author 17.03.2019 04:30 GOOD peoples Please help me! I have got WA#5! I used DSU!! My program gives right answer for all my tests! But again WA#5 and I can not found my mistake! I shall wait advices or tests! Thank you advance!!! I have got AC!!! =) What test you used to check it? 4 4 1 2 1 2 2 3 3 4 3 1 2 3 good luck!!! I used DSU and I have WA16. Can you help me? I can't help you without code. I have never WA#16. I only have several MLE's before AC. "/* const int maxn = 100100; int a[maxn], b[maxn], c[maxn]; bool order[maxn]; int cnt; int p[maxn], rank[maxn]; int find_set(int x) { if(p[x] == x) return x; return p[x] = find_set(p[x]); } int unite(int x, int y) { x = find_set(x); y = find_set(y); if(x == y) return 0; if(rank[x] > rank[y]) { p[y] = x; } else { p[x] = y; if(rank[x] == rank[y]) rank[y] ++; } return 1; } int main() {
int n, m, q; scanf("%d%d", &n, &m); for (int i = 0; i < m; i ++) { scanf("%d%d", a + i, b + i); } scanf("%d", &q); for (int i = 0; i < q; i ++) { scanf("%d", c + i); order[c[i]] = true; } for (int i = 0; i < n; i ++) p[i] = i; cnt = n; for (int i = 0; i < n; i ++) { if(order[i] == false) { cnt = unite(a[i], b[i]); } }
c[q] = cnt; for (int i = q  1; i > 0; i ) { cnt = unite(a[c[i]], b[c[i]]); c[i] = cnt; } for (int i = 1; i < q; i ++) printf("%d ", c[i]); printf("%d", c[q]); }*/" You have a cycle where you are calculating cnt for q. The limit is wrong. i<n is wrong. i<m is correct. Because of m is number of edges not n. I changed n to m in your code and got AC again. Thanks Mahilewets!!! Is your idea same or not ? Idea is the same. I was getting MLE because of critical mistake in find_set. There was an iterative implementation. My iterative function was equivalent to : return (par[x] == x) ? x : par[x] =find_set (x) ; Thanks for your answer ! cause i made the same problem! The good part is Initially I made such mistakes incredible often But after only few months of regular basis practice Such blunders almost completely disappeared 5 7 1 2 2 3 1 4 4 5 1 5 2 5 4 3 4 3 4 7 2 ans: 1 1 2 3 I am not allocating any memory in heap, everything is defined globally, why do I get Memory Limit Exceeded error on test 5? Why this error is not given for test 1? I'm not even using STL. It also happened to me solving another problem(1220. Stacks), I got memory limit exceeded on test 10, same situation as here. Does IO operations use memory? I assume I get this error as testcases get larger in size... (I also tried disabling IO buffering) Solved. It was a problem with my DSU function. Can there be identical threads in the test? Like: 4 4 1 2 1 2 2 3 3 4 3 1 2 3 And if they can occur is the answer 2 2 3 or 1 2 3? My program gives: 1 2 3 I got AC. It is a web. The web is not a multigraph. All edges will be unique. I solve this problem with C++ first and got WA#6, but I can't find where is my problem, so I rewrite it with C# with the same solution, but to my surprise, this time I got AC. And even till now I don't know what are the differences between my two lovely code. Any idea? //Sorry for my poor English Idea  those two solutions are not the same really. What else do you expect w/o any code? BTW, you can write random generator of big tests and run and compare outputs of two solutions till you'll find a difference. I don't think there are such threads as (2 Edges) 1 2 2 1 And although my program can solve that case, I still WA on test5. Can you help me and give me some advice? Thank you very much! Use union+Rank can AC.... Use union+Rank can AC.... Try this test: 4 4 1 2 1 2 2 3 3 4 3 1 2 3 Answer 1 2 3 gimme test, please) 4 4 ** 4 4 1 2 ** 1 4 1 3 ** 2 3 2 3 ** 2 4 3 4 ** 3 4 1 **** 1 4 **** 4 maybe it can help Edited by author 22.01.2009 16:27 it's 2 1 ,my code work ok ,but wrong #5 ,where? Edited by author 20.01.2013 09:13 Try this test case: 4 5 1 2 2 3 3 4 4 2 1 3 5 1 2 3 4 5 The answer is: 1 1 2 3 4 my code do that is right ,but... Try this test: 4 4 1 2 1 2 2 3 3 4 3 1 2 3 Answer: 1 2 3 I had the same problem, and solved it after changing all c++ io functions from <iostream> to <cstdio> Thanks, your hint really helped me. The same thing in Java. I had TLEon15. After I replaced Scanner with my custom input parsing I had got AC. I use Disjointset who can help me? I use graph to solve this problem but initially get MLE. Then I reduce the size of array because of the matrix is a Symmetric Matrix. However,finaly crash at test #9. Can somebody give me some tips? If its not a multy eadge and it is a bridge, then it increase the number of pieces by one otherwise the pieces amount left same. Am I right? Edited by author 11.07.2010 23:42 Sure ;) By the way my DSU got AC with 0.109 sec time and 2 178 KB memory. WHat about you? subj I got AC when i handle multigraphs (multiple edges between pair of vertices are possible) Look my post (he located above your post in that node{ NOT MAIN NODE BUT NODE of the problem 1671}) there you can find test with multiedges. Edited by author 15.01.2010 22:18 Edited by author 16.01.2010 13:03 Are there multiple egdes in the tests? A have WA 25 and i don't process this case. I think there are no multiple edges because [don't_processing_multiple_edges_programm] can't pass 25 tests. Can anybody give me 25 test or some hints? P.S I use dsu with heuristics. Now I got AC. There can be tests with multiedges for example 2 2 1 2 2 1 1 1 answer is 1. Also, don't use STL to avoid TLE. Can you give me some tricky tests, please? I got wa4 too. Maybe we don't undestand the task... Please give some tests. thX what answer for this test? 4 4 1 4 4 1 1 4 4 1 4 4 3 1 2 my ans : 3 3 3 4 You are given a graph, and in each step you cut (remove) one of the edges, you must output (in each step) the amount of components in the new graph. Edited by author 11.01.2009 21:35 
