Submission #580859

#	Time	Username	Problem	Language	Result	Execution time	Memory
580859		8e7	Werewolf (IOI18_werewolf)	C++17	0 / 100	912 ms	77896 KiB

werewolf

//Challenge: Accepted
#include <bits/stdc++.h>
#include "werewolf.h"
#pragma GCC optimize("Ofast")
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 200005
#define mod 1000000007
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
const int inf = 1<<30;
vector<int> adj[maxn], tr[maxn * 2];
vector<int> qi[maxn * 2];
pii ran[maxn];

struct query{
	int s, e, l, r, id;
	query(){s = e = l = r = id = 0;}		
	query(int a, int b, int c, int d, int p) {
		s = a, e = b, l = c, r = d, id = p;
	}
};
struct DSU{
	int id[maxn], par[maxn];
	int cur = 0;
	void init(int n) {
		cur = n;
		for (int i = 0;i < n;i++) {
			id[i] = i;
			par[i] = i;
		}
	}
	int find(int a) {
		return a == par[a] ? a : (par[a] = find(par[a]));
	}
	bool Union(int a, int b) {
		a = find(a), b = find(b);
		if (a == b) return 0;
		tr[cur].push_back(id[a]);
		tr[cur].push_back(id[b]);
		par[b] = a;	
		id[a] = cur;
		cur++;
		return 1;
	}
} d;

set<int> se[maxn];
void combine(int u, int v) {
	if (se[u].size() < se[v].size()) swap(se[u], se[v]);
	for (int p:se[v]) {
		se[u].insert(p);
	}
	se[v].clear();
}
pii dfs(int n) {
	pii ret = {inf, -1};
	for (int v:tr[n]) {
		pii tmp = dfs(v);
		ret = {min(tmp.ff, ret.ff), max(tmp.ss, ret.ss)};
	}
	if (!tr[n].size()) {
		ret = {n, n};
	}
	for (int i:qi[n]) ran[i] = ret;
	return ret;
}

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

	for (int i = 0;i < Q;i++) {
		if (S[i] >= L[i] && E[i] <= R[i]) {
			que.push_back(query(S[i], E[i], L[i], R[i], i));
		}
	}	
	sort(que.begin(), que.end(), [&] (query x, query y){return x.r < y.r;});
	vector<int> ret(Q, 0);	
	for (int i = 0;i < M;i++) {
		adj[X[i]].push_back(Y[i]);
		adj[Y[i]].push_back(X[i]);
	}	
	d.init(N);

	{
		int ind = 0;
		for (int i = 0;i < N;i++) {
			for (int j:adj[i]) {
				if (j < i) {
					d.Union(i, j);
				}
			}
			while (ind < Q && que[ind].r == i) {
				int pos = d.id[d.find(que[ind].e)];
				qi[pos].push_back(que[ind].id);		
				ind++;
			}
		}
	}
	dfs(d.cur - 1);
	sort(que.begin(), que.end(), [&] (query x, query y){return x.l > y.l;});
	{
		d.init(N);
		for (int i = 0;i < N;i++) se[i].insert(i);
		int ind = 0;
		for (int i = N - 1;i >= 0;i--) {
			for (int j:adj[i]) {
				if (j > i) {
					if (d.find(i) != d.find(j)) {
						combine(d.find(i), d.find(j));
						d.Union(i, j);
					}
				}
			}
			while (ind < Q && que[ind].l == i) {
				int p = d.find(que[ind].s);		
				int id = que[ind].id;
				if (se[p].lower_bound(ran[id].ff) != se[p].upper_bound(ran[id].ss)) {
					ret[id] = 1;
				}
				ind++;
			}
		}
	}
	return ret;
}
/*
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 5 3 4
*/

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