Submission #982116

#	Time	Username	Problem	Language	Result	Execution time	Memory
982116		mariaclara	Werewolf (IOI18_werewolf)	C++17	0 / 100	4032 ms	35168 KiB

werewolf

#include "werewolf.h"
#include<bits/stdc++.h>

using namespace std;

typedef pair<int,int> pii;
const int VAL = 500;
const int MAXN = 2e5+5;
#define pb push_back
#define fr first
#define sc second

int pai[MAXN], sz[MAXN];
vector<int> alt;

int find(int x) {
    if(pai[x] == x) return x;
    alt.pb(x);
    return pai[x] = find(pai[x]);
}

void join(int x, int y) {
    x = find(x);
    y = find(y);
    if(x == y) return;
    alt.pb(x);
    alt.pb(y);
    if(sz[x] < sz[y]) {
        pai[x] = y;
        sz[y] += sz[x];
    }
    else {
        pai[y] = x;
        sz[x] += sz[y];
    }
}
vector<int> check_validity(int n, vector<int> X, vector<int> Y,
vector<int> S, vector<int> E, vector<int> L, vector<int> R) {

    int m = (int)X.size(), q = (int)S.size();
    vector<pii> edges;
    vector<vector<int>> graph(n);

    for(int i = 0; i < m; i++) {
        if(X[i] > Y[i]) swap(X[i], Y[i]);
        edges.pb({X[i],Y[i]});
        graph[Y[i]].pb(X[i]);
    }

    sort(edges.begin(), edges.end());
    reverse(edges.begin(), edges.end());

    vector<vector<int>> query(n);
    for(int i = 0; i < q; i++) query[R[i]].pb(i);

    vector<int> ans(q), pre_calc(m), calc(q);

    for(int i = 0; i < m; i++) {
        if(i == 0) pre_calc[0] = X[0];
        else pre_calc[i] = min(pre_calc[i-1], X[i]); 
    }

    vector<int> aux_pai(n), aux_sz(n);
    for(int i = 0; i < n; i++)
        pai[i] = aux_pai[i] = i, sz[i] = aux_sz[i] = 1;

    //for(auto [a,b] : edges) cout << a << " " << b << "\n";
    for(int i = 0, c = 0; i < m; i++) {
        if(VAL * c == i) {
            vector<int> save_pai(n), save_sz(n);
            for(int j = 0; j < n; j++)
                save_pai[j] = aux_pai[j] = pai[j], save_sz[j] = aux_sz[j] = sz[j];

            for(int j = 0; j < n; j++) {
                for(int viz : graph[j])
                    join(j,viz);

                // cout << "testando r = " << j << "\n";    
                // for(int A = 0; A < n; A++)
                //     cout << pai[A] << " \n"[A==n-1];

                for(int it : alt) 
                    aux_pai[it] = pai[it], aux_sz[it] = sz[it];
                alt.clear();

                for(int l : query[j]) {
                    if(L[l] < pre_calc[min(i+VAL-1,m-1)] or calc[l]) continue;

                    for(int k = i; k < min(m, i + VAL); k++) 
                        if(edges[k].fr >= L[l]) join(edges[k].fr, edges[k].sc);
                        else break;

                    // for(int A = 0; A < n; A++)
                    //     cout << pai[A] << " \n"[A==n-1];
                    // cout << "calculo " << j << "\n";

                    if(find(S[l]) == find(E[l])) ans[l] = 1;

                    for(int it : alt)
                        pai[it] = aux_pai[it], sz[it] = aux_sz[it];
                    alt.clear();

                    calc[l] = 1;
                }
            }

            for(int j = 0; j < n; j++)
                pai[j] = save_pai[j], sz[j] = save_sz[j];

            c++;
        }

        join(edges[i].fr, edges[i].sc);
        alt.pop_back();
    }

    return ans;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51