Submission #1042033

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042033		Dan4Life	Werewolf (IOI18_werewolf)	C++17	15 / 100	4065 ms	92076 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
using vi = vector<int>;
using ll = long long;
using ar2 = array<int,2>;
const int mxN = (int)2e5+10;
const int mxLg = 20;
int n,m,q,dfs_timer;
int jmp[2][mxLg][mxN];
int st[2][mxN], en[2][mxN], A[2][mxN];
vector<int> adj[mxN], euler[2], adj2[2][mxN];

template<int SZ> struct DSU{
    int p[SZ], root;
    void init(int n){ for(int i=0; i<n; i++) p[i]=i;}
    int findSet(int i){return p[i]==i?i:p[i]=findSet(p[i]);}
    bool isSameSet(int i, int j) {return findSet(i)==findSet(j);}
    void unionSet(int t, int i, int j){
        int x = findSet(i), y = findSet(j);
        if(x==y) return;
        adj2[t][x].pb(y); root=x, p[y]=x;
    }
};
DSU<mxN> dsu[2];

void dfs(int s, int p, int t){
	st[t][s] = dfs_timer++;
	euler[t].pb(s); jmp[t][0][s] = p;
	for(auto u : adj2[t][s]){
		if(u==p) continue;
		dfs(u,s,t);
	}
	en[t][s] = dfs_timer-1;
}

vi check_validity(int _N, vi U, vi V, vi S, vi T, vi L, vi R) {
	n = _N, m = sz(U), q = sz(S);
	vi ans(q,0); memset(jmp,-1,sizeof(jmp));
	dsu[0].init(n), dsu[1].init(n);
	for(int i = 0; i < m; i++){
		int a = U[i], b = V[i];
		adj[a].pb(b), adj[b].pb(a);
	}
	for(int i = n-1; i >= 0; i--)
		for(auto u : adj[i]) if(u>i) 
			dsu[0].unionSet(0,i,u);
	for(int i = 0; i < n; i++)
		for(auto u : adj[i]) if(u<i) 
			dsu[1].unionSet(1,i,u);
	for(int t : {0,1}){
		dfs_timer = 0; dfs(dsu[t].root, -1, t);
		for(int i = 1; i < mxLg; i++)
			for(int j = 0; j < n; j++)
				jmp[t][i][j] = jmp[t][i-1][jmp[t][i-1][j]];
	}
	for(int i = 0; i < q; i++){
		int s = S[i], t = T[i], l = L[i], r = R[i];
		for(int j = mxLg-1; j>=0; j--){
			if(jmp[0][j][s]!=-1 and jmp[0][j][s]>=l) s = jmp[0][j][s];
			if(jmp[1][j][t]!=-1 and jmp[1][j][t]<=r) t = jmp[1][j][t];
		}
		for(int j = st[0][s]; j <= en[0][s]; j++){
			for(int k = st[1][t]; k <= en[1][t]; k++){
				ans[i]|=(euler[0][j]==euler[1][k]);
			}
		}
	}
	return ans;
}

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