Submission #630374

#	Time	Username	Problem	Language	Result	Execution time	Memory
630374		abeker	Werewolf (IOI18_werewolf)	C++17	100 / 100	3142 ms	259304 KiB

werewolf

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

typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, int> pli;

const int MAXN = 2e5 + 5;

struct dsu {
	int dad[MAXN];
	vector <int> comp[MAXN];
	vector <pii> events[MAXN];
	
	void init(int n, int t) {
		for (int i = 1; i <= n; i++) {
			events[i].push_back({t, i});
			comp[i].push_back(i);
			dad[i] = i;
		}
	}
	
	void join(int x, int y) {
		int timer = x;
		x = dad[x];
		y = dad[y];
		if (x == y)
			return;
		
		if (comp[x].size() > comp[y].size())
			swap(x, y);
		
		for (auto it : comp[x]) {
			events[it].push_back({timer, y});
			comp[y].push_back(it);
			dad[it] = y;
		}
	}
};

dsu up, down;
vector <int> adj[MAXN];
unordered_map <ll, int> mx, has;
vector <int> p[MAXN], f[MAXN];
vector <pli> q[MAXN];
pii where[MAXN];

void inc(vector <int> &v) {
	for (auto &it : v)
		it++;
}

inline ll hsh(pii p) {
	return (ll)MAXN * p.first + p.second;
}

vector <int> check_validity(int N, vector <int> x, vector <int> y, vector <int> st, vector <int> en, vector <int> l, vector <int> r) {
	int M = x.size();
	int Q = st.size();
	
	inc(x);
	inc(y);
	inc(st);
	inc(en);
	inc(l);
	inc(r);
	
	for (int i = 0; i < M; i++) {
		adj[x[i]].push_back(y[i]);
		adj[y[i]].push_back(x[i]);
	}
	
	for (int i = 0; i < Q; i++)
		p[r[i]].push_back(i);
		
	up.init(N, 0);
	for (int i = 1; i <= N; i++) {
		for (auto it : adj[i])
			if (it <= i)
				up.join(i, it);
		for (auto it : p[i])
			where[it].first = up.dad[en[it]];
	}
	
	for (int i = 1; i <= N; i++)
		p[i].clear();
	
	for (int i = 0; i < Q; i++)
		p[l[i]].push_back(i);
		
	down.init(N, N + 1);
	for (int i = N; i; i--) {
		for (auto it : adj[i])
			if (it >= i)
				down.join(i, it);
		for (auto it : p[i])
			where[it].second = down.dad[st[it]];
	}
	
	for (int i = 0; i < Q; i++)
		has[hsh(where[i])] = 1;
	
	for (int i = 1; i <= N; i++) 
		for (auto it1 : up.events[i])
			for (auto it2 : down.events[i]) {
				ll tmp = hsh({it1.second, it2.second});
				if (has[tmp])
					q[it1.first].push_back({tmp, it2.first});
			}
			
	for (int i = 0; i < Q; i++)
		f[r[i]].push_back(i);
		
	vector <int> ans(Q, 0);
	for (int i = 0; i <= N; i++) {
		for (auto it : q[i])
			if (it.second > mx[it.first])
				mx[it.first] = it.second;
		for (auto it : f[i])
			ans[it] = mx[hsh(where[it])] >= l[it];
	}
	
	return ans;
}

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