What 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]