oj.uz

Submission #114718

# Submission time Handle Problem Language Result Execution time Memory
114718 2019-06-02T12:30:17 Z WhipppedCream Werewolf (IOI18_werewolf) C++17
15 / 100
 1389 ms 524288 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;
typedef vector<int> vi;

const int maxn = 2e5+5;

struct dsu
{
	vector<int> par;
	dsu(int n = 0)
	{
		par.resize(n);
		for(int i = 0; i< n; i++) par[i] = i;
	}
	int findset(int x)
	{
		if(x == par[x]) return x;
		return par[x] = findset(par[x]);
	}
};

dsu hum, wolf;

int n, m, q;

vector<int> adj[maxn];

struct tahm
{
	int s, e, l, r, id;
	int hum, wolf;
	tahm(int s, int e, int l, int r, int id): s(s), e(e), l(l), r(r), id(id) {}
};

bool cmpl(tahm a, tahm b)
{
	return a.l< b.l;
}

bool cmpr(tahm a, tahm b)
{
	return a.r< b.r;
}

vector<tahm> kench;
vector<int> twolf[2*maxn];
vector<int> thum[2*maxn];

vector<int> pred;
int numb[maxn];
int lb[2*maxn];
int rb[2*maxn];

void dfs(int u = 2*n-2)
{
	if(u< n) pred.pb(u);
	for(int v : twolf[u]) dfs(v);
}

void calc(int u = 2*n-2)
{
	lb[u] = 1e9, rb[u] = -1;
	if(u< n) lb[u] = rb[u] = numb[u];
	for(int v : twolf[u])
	{
		calc(v);
		lb[u] = min(lb[u], lb[v]);
		rb[u] = max(rb[u], rb[v]);
	}
	// printf("lb[%d] = %d, rb[%d] = %d\n", u, lb[u], u, rb[u]);
}

struct node
{
	int val;
	node *left, *right;
	node(int _val, node* _left, node *_right)
	{
		val = _val; left = _left; right = _right;
	}
	node* insert(int x, int L = 0, int R = n-1)
	{
		if(L<= x && x<= R)
		{
			if(L == R) return new node(val+1, NULL, NULL);
			int M = (L+R)/2;
			return new node(val+1, left->insert(x, L, M), right->insert(x, M+1, R));
		}
		return this;
	}
	int ask(int i, int j, int L = 0, int R = n-1)
	{
		if(i> R || j< L) return 0;
		if(i<= L && R<= j) return val;
		int M = (L+R)/2;
		int x = left->ask(i, j, L, M);
		int y = right->ask(i, j, M+1, R);
		return x+y;
	}
};


node* zero = new node(0, NULL, NULL);

node* roots[2*maxn];
vector<int> elems[2*maxn];

void comb(int u = 2*n-2)
{
	if(u< n)
	{
		elems[u].pb(numb[u]);
		roots[u] = zero->insert(numb[u]);
		return;
	}
	ii big = {0, -1};
	for(int v : thum[u])
	{
		comb(v);
		big = max(big, ii((int) elems[v].size(), v));
	}
	swap(elems[u], elems[big.Y]);
	roots[u] = roots[big.Y];
	for(int v : thum[u])
	{
		for(int x : elems[v])
		{
			elems[u].pb(x);
			roots[u] = roots[u]->insert(x);
		}
		elems[v].clear();
	}
}

vector<int> check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) 
{
	n = N;
	m = X.size();
	q = S.size();
	for(int i = 0; i< q; i++) kench.pb(tahm(S[i], E[i], L[i], R[i], i));
	for(int i = 0; i< m; i++)
	{
		adj[X[i]].pb(Y[i]);
		adj[Y[i]].pb(X[i]);
	}
	wolf = dsu(2*n);
	sort(kench.begin(), kench.end(), cmpr);
	int pt = 0;
	int cnt = n;
	for(int i = 0; i< n; i++)
	{
		for(int v : adj[i])
		{
			if(v< i)
			{
				int a = wolf.findset(i);
				int b = wolf.findset(v);
				if(a == b) continue;
				wolf.par[a] = wolf.par[b] = cnt;
				twolf[cnt].pb(a); 
				twolf[cnt].pb(b);
				// printf("%d-->%d %d-->%d\n", cnt, a, cnt, b);
				cnt++;
			}
		}
		while(pt< q && kench[pt].r == i)
		{
			int e = kench[pt].e;
			int pp = wolf.findset(e);
			kench[pt].wolf = pp;
			pt++;
		}
	}
	// printf("finished wolf\n");
	hum = dsu(2*n);
	sort(kench.begin(), kench.end(), cmpl);
	reverse(kench.begin(), kench.end());
	pt = 0;
	cnt = n;
	for(int i = n-1; i>= 0; i--)
	{
		for(int v : adj[i])
		{
			if(v> i)
			{
				int a = hum.findset(v);
				int b = hum.findset(i);
				if(a == b) continue;
				hum.par[a] = hum.par[b] = cnt;
				// printf("%d->%d, %d->%d\n", cnt, a, cnt, b);
				thum[cnt].pb(a); 
				thum[cnt].pb(b);
				cnt++;				
			}
		}
		while(pt< q && kench[pt].l == i)
		{
			int s = kench[pt].s;
			int pp = hum.findset(s);
			kench[pt].hum = pp;
			pt++;
		}
	}

	dfs();
	// for(int i = 0; i< n; i++) printf("%d ", pred[i]);
	// printf("\n");
	for(int i = 0; i< n; i++) numb[pred[i]] = i;
	calc();
	
	// printf("finished renumbering\n");
	
	zero->left = zero->right = zero;
	comb();
	// printf("%d\n", roots[2*n-2]->ask(0, n-1));
	vector<int> ans(q);
	for(int i = 0; i< q; i++)
	{
		int wolf = kench[i].wolf, hum = kench[i].hum;
		int id = kench[i].id;
		int lo = lb[wolf], hi = rb[wolf];
		// if(hum == 5) printf("wolf is %d [%d %d] ans is %d\n", wolf, lo, hi, roots[hum]->ask(0, 0));
		int res = roots[hum]->ask(lo, hi);
		ans[id] = res> 0;
	}
	return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 33408 KB Output is correct
2 Correct 31 ms 33408 KB Output is correct
3 Correct 30 ms 33260 KB Output is correct
4 Correct 30 ms 33280 KB Output is correct
5 Correct 29 ms 33408 KB Output is correct
6 Correct 29 ms 33408 KB Output is correct
7 Correct 30 ms 33408 KB Output is correct
8 Correct 30 ms 33400 KB Output is correct
9 Correct 29 ms 33408 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 33408 KB Output is correct
2 Correct 31 ms 33408 KB Output is correct
3 Correct 30 ms 33260 KB Output is correct
4 Correct 30 ms 33280 KB Output is correct
5 Correct 29 ms 33408 KB Output is correct
6 Correct 29 ms 33408 KB Output is correct
7 Correct 30 ms 33408 KB Output is correct
8 Correct 30 ms 33400 KB Output is correct
9 Correct 29 ms 33408 KB Output is correct
10 Correct 42 ms 37632 KB Output is correct
11 Correct 42 ms 38008 KB Output is correct
12 Correct 46 ms 39928 KB Output is correct
13 Correct 42 ms 38172 KB Output is correct
14 Correct 47 ms 39672 KB Output is correct
15 Correct 44 ms 37880 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Runtime error 1389 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 33408 KB Output is correct
2 Correct 31 ms 33408 KB Output is correct
3 Correct 30 ms 33260 KB Output is correct
4 Correct 30 ms 33280 KB Output is correct
5 Correct 29 ms 33408 KB Output is correct
6 Correct 29 ms 33408 KB Output is correct
7 Correct 30 ms 33408 KB Output is correct
8 Correct 30 ms 33400 KB Output is correct
9 Correct 29 ms 33408 KB Output is correct
10 Correct 42 ms 37632 KB Output is correct
11 Correct 42 ms 38008 KB Output is correct
12 Correct 46 ms 39928 KB Output is correct
13 Correct 42 ms 38172 KB Output is correct
14 Correct 47 ms 39672 KB Output is correct
15 Correct 44 ms 37880 KB Output is correct
16 Runtime error 1389 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Halted 0 ms 0 KB -