Submission #677772

#	Time	Username	Problem	Language	Result	Execution time	Memory
677772		someone	Werewolf (IOI18_werewolf)	C++14	100 / 100	662 ms	81116 KiB

werewolf

#include <bits/stdc++.h>
using namespace std;
 
const int N = 2e5 + 42;
 
set<int> vals[N];
vector<int> adj[N], fils[N], req[N];
int n, m, q, id = 0, sz[N], par[N], pds[N], deb[N], fin[N];
 
int F(int i) {
    if(par[i] == i)
        return i;
    return par[i] = F(par[i]);
}

void U(int a, int b) {
    a = F(a), b = F(b);
    if(a == b) return;
    if((int)vals[a].size() < (int)vals[b].size())
        swap(a, b);
    par[b] = a;
    for(int i : vals[b])
        vals[a].insert(i);
    vals[b].clear();
}

int nbit = 0;

void dfs(int i) {
    deb[i] = id++;
    for(int j : fils[i])
        dfs(j);
    fin[i] = id;
}

vector<int> check_validity(int NB, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
    n = NB, m = (int)X.size(), q = (int)S.size();
    vector<int> ans(q);
    for(int i = 0; i < n; i++)
        par[i] = i;
    for(int i = 0; i < m; i++) {
        adj[X[i]].push_back(Y[i]);
        adj[Y[i]].push_back(X[i]);
    }
    for(int i = 0; i < q; i++)
        req[L[i]].push_back(i);
    
    for(int i = n-1; i >= 0; i--) {
        for(int j : adj[i])
            if(j > i) {
                j = F(j);
                if(i != j) {
                    fils[i].push_back(j);
                    par[j] = i;
                }
            }
        for(int j : req[i])
            S[j] = F(S[j]);
        req[i].clear();
    }
    
    dfs(0);
    
    for(int i = 0; i < q; i++)
        req[R[i]].push_back(i);
    for(int i = 0; i < n; i++) {
        par[i] = i;
        vals[i].insert(deb[i]);
    }
    for(int i = 0; i < n; i++) {
        for(int j : adj[i])
            if(j < i)
                U(i, j);
        for(int j : req[i]) {
            auto it = vals[F(E[j])].lower_bound(deb[S[j]]);
            if(it != vals[F(E[j])].end() && (*it) < fin[S[j]])
                ans[j] = 1;
        }
    }
    return ans;
}

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