Submission #1234175

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234175		PlayVoltz	Werewolf (IOI18_werewolf)	C++20	0 / 100	167 ms	47140 KiB

werewolf

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

#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

int counter=-1;
vector<int> in, out, dsu, ans, ooga;
vector<vector<int> > graph, query;
vector<set<int> > s;

int fp(int a){
	if (dsu[a]==-1)return a;
	return dsu[a]=fp(dsu[a]);
}

bool merge(int a, int b){
	a=fp(a), b=fp(b);
	if (a==b)return 0;
	dsu[a]=b;
	return 1;
}

void dfs(int node){
	in[node]=++counter;
	for (auto num:graph[node])dfs(num);
	out[node]=counter;
}

void dfs2(int node){
	s[node].insert(in[node]);
	for (auto num:graph[node]){
		dfs2(num);
		if (s[node].size()<s[num].size())swap(s[node], s[num]);
		for (auto a:s[num])s[node].insert(a);
	}
	return;
	for (auto c:query[node]){
		auto it=s[node].lower_bound(in[ooga[c]]);
		if (it!=s[node].end()&&*it<=out[ooga[c]])ans[c]=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){
	counter=-1;
	in.clear();
	out.clear();
	graph.clear();
	dsu.clear();
	ans.clear();
	s.clear();
	ooga.clear();
	query.clear();
	query.resize(n);
	in.resize(n);
	out.resize(n);
	graph.resize(n);
	dsu.resize(n, -1);
	ans.resize(l.size(), 0);
	s.resize(n);
	ooga.resize(l.size());
	vector<vector<int> > adj(n), got(n);
	for (int i=0; i<x.size(); ++i)adj[x[i]].pb(y[i]), adj[y[i]].pb(x[i]);
	for (int i=0; i<l.size(); ++i)got[l[i]].pb(i);
	for (int i=0; i<n; ++i){
		for (auto num:adj[i])if (num<i&&merge(i, num))graph[num].pb(i);
		for (auto num:got[i])ooga[num]=fp(e[num]);
	}
	dfs(0);
	graph.clear();
	graph.resize(n);
	dsu.clear();
	dsu.resize(n, -1);
	got.clear();
	got.resize(n);
	for (int i=0; i<l.size(); ++i)got[r[i]].pb(i);
	for (int i=n-1; i>=0; --i){
		for (auto num:adj[i])if (num>i&&merge(i, num))graph[num].pb(i);
		for (auto num:got[i])query[fp(s[num])].pb(num);
	}
	dfs2(n-1);
	return ans;
}

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