Submission #678353

#	Time	Username	Problem	Language	Result	Execution time	Memory
678353		1bin	Werewolf (IOI18_werewolf)	C++14	100 / 100	846 ms	116992 KiB

werewolf

#include <bits/stdc++.h>

using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
const int B = 1 << 18;
ll n, m, q, par[B], a, b, d[B][2], u[B][2], t;
vector<int> adj[B], seg[B * 2];
vector<int> g[B], vl[B], vr[B];
int find(int x){return par[x] == -1 ? x : par[x] = find(par[x]);}

void dfs(int x, int f){
    !f ? d[x][0] = t++ : u[x][0] = t++;
    for(int& nx : g[x]) dfs(nx, f);
    !f ? d[x][1] = t - 1 : u[x][1] = t - 1;
    return;
}

int qry(int l, int r, int k){
    l += B; r += B;
    int ret = n;
    while(l <= r){
        if(l & 1){
            auto it = lower_bound(all(seg[l]), k);
            if(it != seg[l].end()) ret = min(ret, *it);
            l++;
        }
        if(!(r & 1)){
            auto it = lower_bound(all(seg[r]), k);
            if(it != seg[r].end()) ret = min(ret, *it);
            r--;
        }
        l /= 2; r /= 2;
    }
    return ret;
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
	n = N, m = X.size(), q = S.size();
	vector<int> A(q);
	for(int i = 0; i < m; i++){
	    a = X[i]; b = Y[i];
	    adj[a].emplace_back(b);
	    adj[b].emplace_back(a);
	}
	for(int i = 0; i < q; i++){
	   vl[L[i]].emplace_back(i);
	   vr[R[i]].emplace_back(i);
	}
	memset(par, -1, sizeof(par));
    for(int x = n - 1; x >= 0; x--){
        for(int y : adj[x]){
            if(y < x) continue;
            y = find(y);
            if(x == y) continue;
            par[y] = x;
            g[x].emplace_back(y);
        }
        for(int& i : vl[x])
            S[i] = find(S[i]);
    }
    dfs(0, 0);
    
    memset(par, -1, sizeof(par));
    for(int i = 0; i < n; i++) g[i].clear();
    for(int x = 0; x < n; x++) {
        for(int y : adj[x]){
            if(y > x) continue;
            y = find(y);
            if(x == y) continue;
            par[y] = x;
            g[x].emplace_back(y);
        }
        for(int& i : vr[x])
            E[i] = find(E[i]);
    }
    t = 0; dfs(n - 1, 1);
    for(int i = 0; i < n; i++) seg[B + u[i][0]].emplace_back(d[i][0]);
    for(int i = B - 1; i; i--){
        seg[i].resize(seg[i * 2].size() + seg[i * 2 + 1].size());
        merge(all(seg[i * 2]), all(seg[i * 2 + 1]), seg[i].begin());
    }

    for(int i = 0; i < q; i++){
        a = u[E[i]][0]; b = u[E[i]][1];
        if(qry(a, b, d[S[i]][0]) <= d[S[i]][1]) A[i] = 1;
        else A[i] = 0;
        //cout << i << ' ' << A[i] << '\n';
    }
	return A;
}

/*
int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n >> m >> q;
    vector<int> X(m), Y(m), S(q), E(q), L(q), R(q), ans;
    for(int i = 0; i < m; i++) cin >> X[i] >> Y[i];
    for(int i = 0; i < q; i++) cin >> S[i] >> E[i] >> L[i] >> R[i];
    ans = check_validity(n, X, Y, S, E, L, R);
    for(int i = 0; i < q; i++) cout << ans[i] << ' ';
    return 0;
}*/

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