Submission #254833

#	Time	Username	Problem	Language	Result	Execution time	Memory
254833		arayi	Werewolf (IOI18_werewolf)	C++17	15 / 100	255 ms	49776 KiB

werewolf

#include "werewolf.h"
//Arayi
//#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <math.h>
#include <vector>
#include <cstring>
#include <ctime>
#include <set>
#include <bitset>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <ctime>
#include <climits>
#include <cassert>
#include <chrono>
#include <random>
#include <complex>

#define fr first
#define sc second
#define MP make_pair
#define ad push_back
#define PB push_back
#define fastio ios_base::sync_with_stdio(false); cin.tie(0);
#define lli long long int
#define y1 arayikhalatyan
#define j1 jigglypuff
#define ld long double
#define itn int
#define pir pair<int, int> 
#define all(x) (x).begin(), (x).end()
#define str string
#define enl endl
#define en endl
#define cd complex<long double>
#define vcd vector<cd>
#define vii vector<int>
#define vlli vector<lli>
using namespace std;

const int N = 1e5 + 30;
const lli mod = 1e9 + 7;
const ld pi = acos(-1);
const int T = 238;
const ld e = 1e-13;

int n, q;
vii g[N], l1[N], r1[N], pat, g1[N];
int p[N], sz[N], cll[N], clr[N], col[N];
set<int> fp[N];
int gp(int x)
{
	if (p[x] == x) return x;
	return p[x] = gp(p[x]);
}
void dfs(int v, int l, int r)
{
	cll[v] = l;
	clr[v] = r;
	if (v < n) return;
	int sm = 0;
	for (auto p : g1[v])
	{
		dfs(p, l + sm, l + sm + sz[p] - 1);
		sm += sz[p];
	}
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) 
{
	n = N;
	q = (int)S.size();
	pat.resize(q);
	for (int i = 0; i < q; i++)
	{
		l1[L[i]].ad(i);
		r1[R[i]].ad(i);
	}
	for (int i = 0; i < (int)X.size(); i++)
	{	
		g[X[i]].ad(Y[i]);
		g[Y[i]].ad(X[i]);
	}
	for (int i = 0; i < N; i++) p[i] = i, sz[i] = 1;
	int i1 = n;
	for (int i = n - 1; i >= 0; i--)
	{
		p[i1] = i1;
		sz[i1] = sz[i];
		for (auto p1 : g[i])
		{
			if (p1 > i && gp(p1) != i1)
			{
				int y = gp(p1);
				sz[i1] += sz[y];
				p[y] = i1;
				g1[i1].ad(y);
			}
		}
		g1[i1].ad(i);
		p[i] = i1;
		i1++;
		for (auto p1 : l1[i])
			col[p1] = gp(S[p1]);
	}
	dfs(i1 - 1, 0, n - 1);
	for (int i = 0; i < n; i++) p[i] = i, fp[i].insert(cll[i]);
	for (int i = 0; i < n; i++)
	{
		int mx = 1, i1 = i;
		for (auto p1 : g[i])
		{
			if (p1 < i)
			{
				int y = gp(p1);
				if ((int)fp[y].size() > mx)
				{
					mx = (int)fp[y].size();
					i1 = y;
				}
			}
		}
		p[i] = i1;
		fp[i1].insert(cll[i]);
		for (auto p1 : g[i])
		{
			if (p1 < i && gp(p1) != i1)
			{
				int y = gp(p1);
				p[y] = i1;
				for (auto ii = fp[y].begin(); ii != fp[y].end(); ++ii)
					fp[i1].insert(*ii);
			}
		}
		for (auto p1 : r1[i])
		{
			int x = gp(E[p1]);
			int l = cll[col[p1]], r = clr[col[p1]];
			if (fp[x].lower_bound(l) != fp[x].end() && *fp[x].lower_bound(l) <= r)
			{
				pat[p1] = 1;
			}
			else
			{
				pat[p1] = 0;
			}
		}
	}
	return pat;
}

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