Submission #421580

#	Time	Username	Problem	Language	Result	Execution time	Memory
421580		Keshi	Werewolf (IOI18_werewolf)	C++17	100 / 100	3676 ms	357688 KiB

werewolf

//In the name of God
#include <bits/stdc++.h>
#include "werewolf.h"
#pragma GCC optimize("O2")
#pragma GCC optimize("unroll-loops")
using namespace std;

typedef int ll;
typedef pair<ll, ll> pll;

const ll maxn = 2e5 + 100;
const ll mod = 1e9 + 7;
const ll inf = 1e9;

#define fast_io ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
#define Mp make_pair
#define F first
#define S second
#define Sz(x) ll((x).size())
#define all(x) (x).begin(), (x).end()

int n, m, q;
int dsu[maxn];
vector<int> g[maxn], vec[maxn], h[maxn];
vector<pll> com[maxn];
map<ll, ll> mp[maxn];

void init(bool f = 1){
	for(ll i = 0; i < n; i++){
		dsu[i] = i;
      	vec[i].clear();
		vec[i].reserve(10);
		vec[i].pb(i);
		if(f) mp[i][i] = n;
      	if(f) com[i].reserve(10);
		if(f) com[i].pb(Mp(i, n));
	}
}
bool Union(ll v, ll u, ll i){
	v = dsu[v];
	u = dsu[u];
	if(v == u) return 0;
	if(Sz(vec[v]) < Sz(vec[u])) swap(v, u);
	for(ll x : vec[u]){
		vec[v].pb(x);
		dsu[x] = v;
		mp[x][v] = i;
		com[x].pb(Mp(v, i));
	}
	return 1;
}
bool merge(ll v, ll u){
	v = dsu[v];
	u = dsu[u];
	if(v == u) return 0;
	if(Sz(vec[v]) < Sz(vec[u])) swap(v, u);
	for(ll x : vec[u]){
		vec[v].pb(x);
		dsu[x] = v;
	}
	for(pll x : mp[u]){
		mp[v][x.F] = max(mp[v][x.F], x.S);
	}
	return 1;
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R){
	m = Sz(X);
	q = Sz(S);
	n = N;
	init();
	for(ll i = 0; i < m; i++){
		g[X[i]].pb(Y[i]);
		g[Y[i]].pb(X[i]);
	}
	for(ll i = 0; i < q; i++){
		h[R[i]].pb(i);
	}
	for(ll i = n; i--;){
		for(ll j : g[i]){
			if(j >= i) Union(i, j, i);
		}
	}
	init(0);
	vector<int> ans(q);
	for(ll i = 0; i < n; i++){
		for(ll j : g[i]){
			if(i >= j) merge(i, j);
		}
		for(ll j : h[i]){
			ll mx = 0;
			ll e = dsu[E[j]];
			for(pll x : com[S[j]]){
				mx = max(mx, min(x.S, mp[e][x.F]));
			}
			if(mx >= L[j]) ans[j] = 1;
		}
	}
	return ans;
}

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