Submission #155450

#	Time	Username	Problem	Language	Result	Execution time	Memory
155450		imyujin	Werewolf (IOI18_werewolf)	C++17	100 / 100	1581 ms	105404 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;

#define rb(x) ((x)&(-(x)))

const int MAXN = 200010;
const int MX = 1 << 20;

int N;
int u[MAXN], d[MAXN];
int dot[MAXN];
vector<int> qry[MAXN];
vector<int> ed[MAXN];
int bit[MX];

struct TREE {
	int par[20][MAXN], uni[MAXN];
	vector<int> chi[MAXN];
	int dfn[MAXN], dfr[MAXN];

	int dfs(int x, int d) {
		dfn[x] = dfr[x] = d;
		for(auto a : chi[x]) dfr[x] = dfs(a, dfr[x] + 1);
		return dfr[x];
	}

	int cnttt = 0;
	int guni(int x) { 
		//if(++cnttt < 100) printf("uni[%d] = %d, %d\n", x, uni[x], ~uni[x]);	
		return ~uni[x] ? uni[x] = guni(uni[x]) : x;
	}

	void init() {
		memset(par, 0, sizeof(par));
		memset(uni, -1, sizeof(uni));
		for(int i = N - 1; i >= 0; i--) for(auto a : ed[i]) if(a > i) {
			//printf("%d\n", a);
			int x = guni(a);
			if(x != i) {
				par[0][x] = uni[x] = i;
				chi[i].push_back(x);
			}
		}
		for(int i = 1; i < 20; i++) for(int j = 0; j < N; j++) par[i][j] = par[i - 1][par[i - 1][j]];
		dfs(0, 1);
		//for(int i = 0; i < N; i++) printf("%d ", dfn[i]);
		//printf("\n");
	}

	int gr(int x, int l) {
		for(int i = 19; i >= 0; i--) if(par[i][x] >= l) x = par[i][x];
		return x;
	}
} hm, ww;

void updbit(int x) { for(; x < MX; x += rb(x)) bit[x]++; }
int gbit(int x) {
	int ans = 0;
	for(; x; x -= rb(x)) ans += bit[x];
	return ans;
}
int gbit(int x, int y) { return gbit(y) - gbit(x - 1); }

vector<int> check_validity(int NN, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
	N = NN;
	int M = X.size(), Q = S.size();

	//printf("*\n");
	for(int i = 0; i < M; i++) {
		ed[X[i]].push_back(Y[i]);
		ed[Y[i]].push_back(X[i]);
	}
	hm.init();
	for(int i = 0; i < N; i++) ed[i].clear();
	for(int i = 0; i < M; i++) {
		ed[N - X[i] - 1].push_back(N - Y[i] - 1);
		ed[N - Y[i] - 1].push_back(N - X[i] - 1);
	}
	ww.init();
	for(int i = 0; i < N; i++) dot[hm.dfn[i]] = ww.dfn[N - i - 1];
	//for(int i = 1; i <= N; i++) printf("%d ", dot[i]);

	for(int i = 0; i < Q; i++) {
		int t = hm.gr(S[i], L[i]);
		qry[hm.dfn[t] - 1].push_back(- i - 1);
		qry[hm.dfr[t]].push_back(i);
		t = ww.gr(N - E[i] - 1, N - R[i] - 1);
		d[i] = ww.dfn[t];
		u[i] = ww.dfr[t];
	}

	vector<int> ans(Q);
	for(int i = 1; i <= N; i++) {
		updbit(dot[i]);
		for(auto a : qry[i]) {
			if(a >= 0) ans[a] += gbit(d[a], u[a]);
			else ans[-a - 1] -= gbit(d[-a - 1], u[-a - 1]);
		}
	}
	for(auto &a : ans) a = min(a,1);
	return ans;
	return X;
}

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