Submission #421626

#	Time	Username	Problem	Language	Result	Execution time	Memory
421626		amoo_safar	Werewolf (IOI18_werewolf)	C++17	100 / 100	811 ms	87960 KiB

werewolf

#include "werewolf.h"

#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 2e5 + 10;

int n, m, q;

vector<int> V[N], G[N];
int par[N];
int pos[N];

void Merge(int u, int v){
	u = par[u]; v = par[v];
	if(u == v) return ;
	if(V[u].size() > V[v].size()) swap(u, v);
	for(auto x : V[u]){
		pos[x] = V[v].size();
		par[x] = v;
		V[v].pb(x);
	}
	V[u].clear();
}

vector<pii> Q[2][N];
pii res[2][N];
vi arr[2];

void DSU(vi ord, int z){
	fill(pos, pos + n, 0);
	iota(par, par + n, 0);
	for(int i = 0; i < n; i++) V[i] = {i};

	vector<int> mk(n, 0);
	for(auto u : ord){
		mk[u] = 1;
		for(auto adj : G[u])
			if(mk[adj])
				Merge(adj, u);
		for(auto [id, v] : Q[z][u]){
			res[z][id] = {-pos[v], -pos[v] + ((int) V[par[v]].size())};
		}
	}
	for(auto u : ord)
		for(auto [id, v] : Q[z][u])
			res[z][id].F += pos[v], res[z][id].S += pos[v];
	arr[z] = V[par[0]];
}


typedef array<int, 3> que; // pos fac q_id
int sum[N];
vector<que> tsk[N];

int fen[N];
void AF(int idx, int x){
	for(; idx < N; idx += idx & (-idx))
		fen[idx] += x;
}
int GF(int idx){
	int sm = 0;
	for(; idx; idx -= idx & (-idx))
		sm += fen[idx];
	return sm;
}

void Solve(){
	for(int i = 0; i < n; i++){
		// cerr << "! " << pos[arr[0][i]] << '\n';
		AF(pos[ arr[0][i] ] + 1, +1);
		for(auto [ps, fac, q_id] : tsk[i + 1]){
			sum[q_id] += fac * GF(ps);
		}
	}
}

vi check_validity(int _n, vi X, vi Y,
								vi S, vi E,
								vi L, vi R) {
	
	n = _n;
	m = X.size();
	q = S.size();
	
	for(int i = 0; i < q; i++){
		Q[0][R[i]].pb({i, E[i]});
		Q[1][L[i]].pb({i, S[i]});
	}

	for(int i = 0; i < m; i++) G[X[i]].pb(Y[i]), G[Y[i]].pb(X[i]);
	vector<int> ord(n, 0); iota(all(ord), 0);
	DSU(ord, 0);
	reverse(all(ord));
	DSU(ord, 1);

	// for(int i = 0; i < 2; i++){
	// 	cerr << "! ";
	// 	for(auto x : arr[i]) cerr << x << ' ';
	// 	cerr << '\n';
	// }

	for(int i = 0; i < q; i++){
		auto [l0, r0] = res[0][i];
		auto [l1, r1] = res[1][i];
		tsk[r0].pb({r1, +1, i});
		tsk[r0].pb({l1, -1, i});
		tsk[l0].pb({r1, -1, i});
		tsk[l0].pb({l1, +1, i});
		// cerr << "? [" << l0 << ", " << r0 << ") & [" << l1 << ' ' << r1 << ")\n";
		// break;
	}
	Solve();
	vector<int> ans;
	for(int i = 0; i < q; i++)
		ans.pb(sum[i] ? 1 : 0);
	return ans;
}

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