|
|
back to boardWhat about WA16 ? I used DSU and I have WA16. Can you help me? Re: What about WA16 ? I can't help you without code. I have never WA#16. I only have several MLE's before AC. Re: What about WA16 ? "/* 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]); }*/" Re: What about WA16 ? 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. Re: What about WA16 ? Thanks Mahilewets!!! Is your idea same or not ? Re: What about WA16 ? 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) ; Re: What about WA16 ? Posted by fex 9 Aug 2017 13:10 Thanks for your answer ! cause i made the same problem! Re: What about WA16 ? 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 Re: What about WA16 ? Posted by Abid29 20 May 2020 00:58 i do exactly same mistake and get wa at test 16 thnx Mahilewets Nikita [BSUIR] |
|
|