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

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

WA on 6. Can anyone tell me why?
Послано raphaelrbr 17 мар 2019 04:29
#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[q-i] = 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[q-i] = num;

        }

        for(int i = 1; i<=q; i++){
            cout << ans[i] << " ";
        }



        cout << "\n";


        return 0;
    }











Edited by author 17.03.2019 04:30