oj.uz

Submission #114712

# Submission time Handle Problem Language Result Execution time Memory
114712 2019-06-02T12:24:37 Z WhipppedCream Werewolf (IOI18_werewolf) C++17
15 / 100
 1373 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 = 4e5+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[maxn];
vector<int> thum[maxn];

vector<int> pred;
int numb[maxn];
int lb[maxn];
int rb[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[maxn];
vector<int> elems[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);
		}
	}
}

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 34 ms 38008 KB Output is correct
2 Correct 32 ms 38016 KB Output is correct
3 Correct 33 ms 37880 KB Output is correct
4 Correct 33 ms 38016 KB Output is correct
5 Correct 33 ms 38016 KB Output is correct
6 Correct 34 ms 38016 KB Output is correct
7 Correct 35 ms 38016 KB Output is correct
8 Correct 34 ms 38008 KB Output is correct
9 Correct 35 ms 38008 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 38008 KB Output is correct
2 Correct 32 ms 38016 KB Output is correct
3 Correct 33 ms 37880 KB Output is correct
4 Correct 33 ms 38016 KB Output is correct
5 Correct 33 ms 38016 KB Output is correct
6 Correct 34 ms 38016 KB Output is correct
7 Correct 35 ms 38016 KB Output is correct
8 Correct 34 ms 38008 KB Output is correct
9 Correct 35 ms 38008 KB Output is correct
10 Correct 48 ms 42360 KB Output is correct
11 Correct 46 ms 42616 KB Output is correct
12 Correct 49 ms 44664 KB Output is correct
13 Correct 47 ms 42872 KB Output is correct
14 Correct 50 ms 44408 KB Output is correct
15 Correct 47 ms 42616 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Runtime error 1373 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 34 ms 38008 KB Output is correct
2 Correct 32 ms 38016 KB Output is correct
3 Correct 33 ms 37880 KB Output is correct
4 Correct 33 ms 38016 KB Output is correct
5 Correct 33 ms 38016 KB Output is correct
6 Correct 34 ms 38016 KB Output is correct
7 Correct 35 ms 38016 KB Output is correct
8 Correct 34 ms 38008 KB Output is correct
9 Correct 35 ms 38008 KB Output is correct
10 Correct 48 ms 42360 KB Output is correct
11 Correct 46 ms 42616 KB Output is correct
12 Correct 49 ms 44664 KB Output is correct
13 Correct 47 ms 42872 KB Output is correct
14 Correct 50 ms 44408 KB Output is correct
15 Correct 47 ms 42616 KB Output is correct
16 Runtime error 1373 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Halted 0 ms 0 KB -