oj.uz

Submission #1060465

# Submission time Handle Problem Language Result Execution time Memory
1060465 2024-08-15T15:27:14 Z jamjanek Werewolf (IOI18_werewolf) C++14
100 / 100
 475 ms 131832 KB 
#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn = 200010;
vector<int>graf[maxn];
int father1[maxn], father2[maxn], ojciec1[maxn], ojciec2[maxn];
int find1(int x){
	if(father1[x] == x)return x;
	return father1[x] = find1(father1[x]);
}
int find2(int x){
	if(father2[x] == x)return x;
	return father2[x] = find2(father2[x]);
}
int pre[maxn], post[maxn], preit = -1;
vector<int>graf2[maxn], graf1[maxn];

void dfs(int x){
	pre[x] = ++preit;
	for(auto j: graf1[x])
		dfs(j);
	post[x] = preit;
}




int jump1[maxn][19], jump2[maxn][19];

vector<int> A;
int ustawione[maxn];
vector<pair<pair<int,int>, int>>przedzialy[maxn];

const int base = 1<<18;
vector<int>tree[2*base];

void dodaj(int w, int l, int p, int a, int b, int index){
	if(l>b || p<a)return;
	if(a<=l && p<=b){
		tree[w].push_back(index);
		return;
	}
	dodaj(w*2, l, (l+p)/2, a, b, index);
	dodaj(w*2+1, (l+p)/2+1, p, a, b, index);
}

void usun(int x){
	x+=base;
	while(x>0){
		while(tree[x].size()){
			if(ustawione[tree[x].back()]==1)tree[x].pop_back();
			else{
				A[tree[x].back()] = 1;
				ustawione[tree[x].back()] = 1;
				tree[x].pop_back();
			}
		}
		x/=2;
	}
}

void dfs2(int x){
	for(auto j: przedzialy[x]){
		dodaj(1, 0, base-1, j.first.first, j.first.second, j.second);
	}
	usun(pre[x]);
	
	for(auto j: graf2[x])
		dfs2(j);
	for(auto j: przedzialy[x]){
		ustawione[j.second] = 1;
	}

}



std::vector<int> check_validity(int n, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
	int i;
	for(i=0;i<(int)X.size();i++){
		graf[Y[i]].push_back(X[i]);
		graf[X[i]].push_back(Y[i]);
	}
	for(i=0;i<n;i++)
		ojciec1[i] = n, ojciec2[i] = -1, father1[i] = father2[i] = i;
	for(i=0;i<n;i++){
		for(auto j: graf[i])
			if(j<i){
				if(find1(j) != i)ojciec1[find1(j)] = i;
				father1[find1(j)] = i;
			}
	}
	for(i=n-1;i>=0;i--)
		for(auto j: graf[i])
			if(j>i){
				if(find2(j) != i)ojciec2[find2(j)] = i;
				father2[find2(j)] = i;
			}
	for(i=0;i<n;i++){
		graf1[ojciec1[i]].push_back(i);
		graf2[ojciec2[i]].push_back(i);
	}
//	for(i=0;i<n;i++)printf("%d ", ojciec1[i]);printf("\n");
//	for(i=0;i<n;i++)printf("%d ", ojciec2[i]);printf("\n");
//	return {};
	for(i=0;i<n;i++){
		jump1[i][0] = ojciec1[i];
		if(jump1[i][0] == n)jump1[i][0] = i;
	}
	for(i=0;i<n;i++){
		jump2[i][0] = ojciec2[i];
		if(jump2[i][0] == -1)jump2[i][0] = i;
	}
	for(int j=1;j<18;j++)
		for(int i=0;i<n;i++){
			jump1[i][j] = jump1[jump1[i][j-1]][j-1];
			jump2[i][j] = jump2[jump2[i][j-1]][j-1];
		}
	dfs(n);
//	for(i=0;i<n;i++)printf("%d ", pre[i]);printf("\n");
//	for(i=0;i<n;i++)printf("%d ", post[i]);printf("\n");
	int q = S.size();
	A.resize(q, 0);
	for (int i = 0; i < q; ++i) {
		if(E[i]>R[i] || S[i]<L[i])continue;
		int pom1 = E[i], pom2 = S[i];
		for(int j = 17;j>=0;j--){
//			printf("%d %d\n", pom1, pom2);
			if(jump1[pom1][j]<=R[i])
				pom1 = jump1[pom1][j];
			if(jump2[pom2][j]>=L[i])
				pom2 = jump2[pom2][j];
		}
//		pocz = pre[pom1], kon = post[pom1], it = i;
//		dfs2(pom2);
//		printf("%d: %d %d %d %d\n", i, pom1, pom2, pocz, kon);
		przedzialy[pom2].push_back({{pre[pom1], post[pom1]},i});
	}
	preit = 0;
	for(i=0;i<n;i++)
		if(ojciec2[i]==-1)
			dfs2(i);
	return A;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 33368 KB Output is correct
2 Correct 12 ms 33372 KB Output is correct
3 Correct 12 ms 33332 KB Output is correct
4 Correct 12 ms 33484 KB Output is correct
5 Correct 11 ms 33468 KB Output is correct
6 Correct 12 ms 33372 KB Output is correct
7 Correct 12 ms 33372 KB Output is correct
8 Correct 13 ms 33372 KB Output is correct
9 Correct 12 ms 33372 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 33368 KB Output is correct
2 Correct 12 ms 33372 KB Output is correct
3 Correct 12 ms 33332 KB Output is correct
4 Correct 12 ms 33484 KB Output is correct
5 Correct 11 ms 33468 KB Output is correct
6 Correct 12 ms 33372 KB Output is correct
7 Correct 12 ms 33372 KB Output is correct
8 Correct 13 ms 33372 KB Output is correct
9 Correct 12 ms 33372 KB Output is correct
10 Correct 18 ms 34648 KB Output is correct
11 Correct 15 ms 34396 KB Output is correct
12 Correct 15 ms 34524 KB Output is correct
13 Correct 16 ms 34652 KB Output is correct
14 Correct 15 ms 34544 KB Output is correct
15 Correct 16 ms 34648 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 394 ms 102732 KB Output is correct
2 Correct 404 ms 115876 KB Output is correct
3 Correct 396 ms 121904 KB Output is correct
4 Correct 386 ms 119048 KB Output is correct
5 Correct 385 ms 116796 KB Output is correct
6 Correct 415 ms 114380 KB Output is correct
7 Correct 344 ms 115852 KB Output is correct
8 Correct 387 ms 123576 KB Output is correct
9 Correct 368 ms 119492 KB Output is correct
10 Correct 285 ms 111620 KB Output is correct
11 Correct 297 ms 109140 KB Output is correct
12 Correct 322 ms 112268 KB Output is correct
13 Correct 420 ms 131456 KB Output is correct
14 Correct 466 ms 129944 KB Output is correct
15 Correct 441 ms 130192 KB Output is correct
16 Correct 439 ms 130324 KB Output is correct
17 Correct 358 ms 115132 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 33368 KB Output is correct
2 Correct 12 ms 33372 KB Output is correct
3 Correct 12 ms 33332 KB Output is correct
4 Correct 12 ms 33484 KB Output is correct
5 Correct 11 ms 33468 KB Output is correct
6 Correct 12 ms 33372 KB Output is correct
7 Correct 12 ms 33372 KB Output is correct
8 Correct 13 ms 33372 KB Output is correct
9 Correct 12 ms 33372 KB Output is correct
10 Correct 18 ms 34648 KB Output is correct
11 Correct 15 ms 34396 KB Output is correct
12 Correct 15 ms 34524 KB Output is correct
13 Correct 16 ms 34652 KB Output is correct
14 Correct 15 ms 34544 KB Output is correct
15 Correct 16 ms 34648 KB Output is correct
16 Correct 394 ms 102732 KB Output is correct
17 Correct 404 ms 115876 KB Output is correct
18 Correct 396 ms 121904 KB Output is correct
19 Correct 386 ms 119048 KB Output is correct
20 Correct 385 ms 116796 KB Output is correct
21 Correct 415 ms 114380 KB Output is correct
22 Correct 344 ms 115852 KB Output is correct
23 Correct 387 ms 123576 KB Output is correct
24 Correct 368 ms 119492 KB Output is correct
25 Correct 285 ms 111620 KB Output is correct
26 Correct 297 ms 109140 KB Output is correct
27 Correct 322 ms 112268 KB Output is correct
28 Correct 420 ms 131456 KB Output is correct
29 Correct 466 ms 129944 KB Output is correct
30 Correct 441 ms 130192 KB Output is correct
31 Correct 439 ms 130324 KB Output is correct
32 Correct 358 ms 115132 KB Output is correct
33 Correct 475 ms 111700 KB Output is correct
34 Correct 211 ms 78384 KB Output is correct
35 Correct 473 ms 115664 KB Output is correct
36 Correct 453 ms 111172 KB Output is correct
37 Correct 459 ms 114380 KB Output is correct
38 Correct 451 ms 112160 KB Output is correct
39 Correct 449 ms 117556 KB Output is correct
40 Correct 445 ms 130884 KB Output is correct
41 Correct 363 ms 110288 KB Output is correct
42 Correct 299 ms 107108 KB Output is correct
43 Correct 464 ms 121980 KB Output is correct
44 Correct 407 ms 111900 KB Output is correct
45 Correct 378 ms 121336 KB Output is correct
46 Correct 397 ms 123296 KB Output is correct
47 Correct 422 ms 131832 KB Output is correct
48 Correct 440 ms 130764 KB Output is correct
49 Correct 444 ms 130988 KB Output is correct
50 Correct 429 ms 130068 KB Output is correct
51 Correct 435 ms 129804 KB Output is correct
52 Correct 433 ms 129488 KB Output is correct