Submission #1192399

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192399		nguyn	늑대인간 (IOI18_werewolf)	C++20	100 / 100	573 ms	108084 KiB

werewolf

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

#define ll long long 
#define F first
#define S second
#define pb push_back 
#define pii pair<int,int>

const int N = 2e5 + 5;

struct Edge {
	int u, v, w; 

	Edge(int _u, int _v, int _w) : u(_u), v(_v), w(_w) {}

	bool operator < (const Edge &o) const {
		return w < o.w; 
	}
};

vector<Edge> edges; 

vector<int> g[2 * N]; 

struct DSU {
	int n; 
	vector<int> par; 

	DSU() {}
 	DSU(int n) : n(n) {
		par.resize(n); 
		for (int i = 0; i < n; i++) par[i] = i; 
	}
	
	int find(int x) {
		return par[x] == x ? x : par[x] = find(par[x]); 
	}

	void join(int x, int y) {
		if ((x = find(x)) == (y = find(y))) return; 
		par.emplace_back(); 
		par[y] = par[x] = par[n] = n; 
		g[n].pb(x);
		g[n].pb(y); 
		// cout << n << ' ' << x << endl;
		// cout << n << ' ' << y << endl;
		n++; 
	}
	
} dsu;

int n, m, q; 
int pos[2 * N]; 
int st[2 * N]; 
int en[2 * N]; 
int st1[2 * N];
int en1[2 * N]; 
int up[2 * N][20]; 
int a[2 * N]; 
pii range1[N];
pii range2[N];
int timedfs;
vector<pii> event[2 * N];

void dfs(int u, int p, int type) {
	st[u] = ++timedfs; 
	a[u] = u;
	if (type) {
		if (u >= n) a[u] = 0;
	}
	for (int v : g[u]) {
		if (v == p) continue; 
		up[v][0] = u;
		for (int i = 1; i < 20; i++) {
			if (up[v][i - 1] != -1) up[v][i] = up[up[v][i - 1]][i - 1];
		}
		dfs(v, u, type); 
		if (!type) a[u] = min(a[u], a[v]); 
		else a[u] = max(a[u], a[v]);
	}
	// cout << u << ' ' << a[u] << endl;
	en[u] = timedfs; 
}

int jump(int u, int bound, int type) {
	if (type == 0) {
		for (int i = 19; i >= 0; i--) {
			if (up[u][i] != -1 && a[up[u][i]] >= bound) {
				u = up[u][i];
			}
		}
		return u;
	}
	else {
		for (int i = 19; i >= 0; i--) {
			if (up[u][i] != -1 && a[up[u][i]] <= bound) {
				u = up[u][i];
			}
		}
		return u;		
	}
}

int bit[2 * N];
void update(int id, int val) {
	if (id == 0) return;
	for (int i = id; i < 2 * n; i += (i & -i)) bit[i] += val;
}

int get(int id) {
	int res = 0;
	for (int i = id; i > 0; i -= (i & -i)) res += bit[i];
	return res; 
}

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(); 
	dsu = DSU(n); 
	for (int i = 0; i < m; i++) {
		if (X[i] < Y[i]) swap(X[i], Y[i]); 
		edges.emplace_back(X[i], Y[i], Y[i]); 
	}
	sort(edges.begin(), edges.end()); 
	for (int i = m - 1; i >= 0; i--) {
		dsu.join(edges[i].u, edges[i].v); 
	}
	int root = dsu.n;
	memset(up, -1, sizeof(up));
	dfs(root - 1, -1, 0);
	for (int i = 0; i < q; i++) {
		int anc = jump(S[i], L[i], 0);
		// cout << anc << endl;
		range1[i] = {st[anc], en[anc]}; 
	}
	for (int i = 0; i <= root; i++) {
		st1[i] = st[i];
		en1[i] = en[i];
	}
	edges.clear(); 
	for (int i = 0; i < root; i++) g[i].clear(); 
	for (int i = 0; i < m; i++) {
		edges.emplace_back(X[i], Y[i], X[i]);
	}
	dsu = DSU(n); 
	sort(edges.begin(), edges.end()); 
	for (int i = 0; i < m; i++) {
		dsu.join(edges[i].u, edges[i].v); 
	}
	root = dsu.n;
	memset(up, -1, sizeof(up));
	timedfs = 0;
	dfs(root - 1, -1, 1); 
	// for (int i = 0; i < root; i++) {
	// 	cout << a[i] << ' ';
	// }cout << '\n';
	// for (int i = 0; i < root; i++) {
	// 	cout << i << endl;
	// 	for (int j = 0; j < 3; j++) {
	// 		cout << up[i][j] << ' ';
	// 	} cout << '\n';
	// }cout << '\n';
	for (int i = 0; i < q; i++) {
		int anc = jump(E[i], R[i], 1);
		// cout << anc << endl;
		range2[i] = {st[anc], en[anc]}; 
	}
	for (int i = 0; i < n; i++) {
		// cout << st1[i] << ' ' << st[i] << endl;
		pos[st1[i]] = st[i]; 
	}
	for (int i = 0; i < q; i++) {
		event[range1[i].S].pb({i, 1});
		event[range1[i].F - 1].pb({i, -1});
	}
	vector<int> res(q); 
	for (int i = 1; i <= root; i++) {
		update(pos[i], 1); 
		for (auto it : event[i]) {
			res[it.F] += (get(range2[it.F].S) - get(range2[it.F].F - 1)) * it.S; 
		}
	}
	for (int i = 0; i < q; i++) {
		res[i] = (res[i] > 0); 
	}
	return res;
}	

// vector<int> X, Y, S, E, L, R;


// signed main(){
//     ios_base::sync_with_stdio(false) ; 
//     cin.tie(0) ; cout.tie(0) ; 
//     if (fopen("INP.INP" ,"r")) {
//         freopen("INP.INP" ,"r" , stdin) ;
//         freopen("OUT.OUT" , "w" , stdout) ;
//     }
//     cin >> n >> m >> q; 
//     X.resize(m);
//     Y.resize(m);
//     S.resize(q);
//     E.resize(q);
//     L.resize(q);
//     R.resize(q); 
//     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]; 
//     }
//   	vector<int> res = check_validity(n, X, Y, S, E, L, R); 
//   	for (int i = 0; i < q; i++) {
//   		cout << res[i] << '\n';
//   	}
// }	

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