ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1671. Паутина Ананси

What about WA16 ?
Послано Khujamurod 6 июл 2017 13:46
I used DSU and I have WA16. Can you help me?
Re: What about WA16 ?
Послано Mahilewets 6 июл 2017 14:55
I can't help you without code.
I have never WA#16.
I only  have several MLE's before AC.
Re: What about WA16 ?
Послано Khujamurod 6 июл 2017 19:14
"/*
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 ?
Послано Mahilewets 6 июл 2017 22:07
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 ?
Послано Khujamurod 7 июл 2017 09:40
Thanks Mahilewets!!! Is your idea same or not ?
Re: What about WA16 ?
Послано Mahilewets 7 июл 2017 13:34
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 ?
Послано fex 9 авг 2017 13:10
Thanks for your answer ! cause i made the same problem!
Re: What about WA16 ?
Послано Mahilewets Nikita [BSUIR] 9 авг 2017 13:41
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 ?
Послано Abid29 20 май 2020 00:58
i do exactly same mistake and get wa at test 16
thnx Mahilewets Nikita [BSUIR]