oj.uz

Submission #1060460

# Submission time Handle Problem Language Result Execution time Memory
1060460 2024-08-15T15:18:35 Z jamjanek Werewolf (IOI18_werewolf) C++14
15 / 100
 4000 ms 88148 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;
}

vector<int> A;

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

int pocz, kon, it;
void dfs2(int x){
//	printf("%d %d\n", x, graf2[x].size());
	if(pocz<=pre[x] && pre[x]<=kon)
		A[it] = 1;
	for(auto j: graf2[x])
		dfs2(j);
}

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

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;
//	dfs2(n);
	return A;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 20312 KB Output is correct
2 Correct 7 ms 20316 KB Output is correct
3 Correct 7 ms 20316 KB Output is correct
4 Correct 7 ms 20236 KB Output is correct
5 Correct 7 ms 20316 KB Output is correct
6 Correct 9 ms 20312 KB Output is correct
7 Correct 7 ms 20216 KB Output is correct
8 Correct 7 ms 20316 KB Output is correct
9 Correct 7 ms 20460 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 20312 KB Output is correct
2 Correct 7 ms 20316 KB Output is correct
3 Correct 7 ms 20316 KB Output is correct
4 Correct 7 ms 20236 KB Output is correct
5 Correct 7 ms 20316 KB Output is correct
6 Correct 9 ms 20312 KB Output is correct
7 Correct 7 ms 20216 KB Output is correct
8 Correct 7 ms 20316 KB Output is correct
9 Correct 7 ms 20460 KB Output is correct
10 Correct 37 ms 21440 KB Output is correct
11 Correct 28 ms 21416 KB Output is correct
12 Correct 10 ms 21336 KB Output is correct
13 Correct 21 ms 21512 KB Output is correct
14 Correct 10 ms 21436 KB Output is correct
15 Correct 28 ms 21340 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1109 ms 79116 KB Output is correct
2 Execution timed out 4062 ms 88148 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 20312 KB Output is correct
2 Correct 7 ms 20316 KB Output is correct
3 Correct 7 ms 20316 KB Output is correct
4 Correct 7 ms 20236 KB Output is correct
5 Correct 7 ms 20316 KB Output is correct
6 Correct 9 ms 20312 KB Output is correct
7 Correct 7 ms 20216 KB Output is correct
8 Correct 7 ms 20316 KB Output is correct
9 Correct 7 ms 20460 KB Output is correct
10 Correct 37 ms 21440 KB Output is correct
11 Correct 28 ms 21416 KB Output is correct
12 Correct 10 ms 21336 KB Output is correct
13 Correct 21 ms 21512 KB Output is correct
14 Correct 10 ms 21436 KB Output is correct
15 Correct 28 ms 21340 KB Output is correct
16 Correct 1109 ms 79116 KB Output is correct
17 Execution timed out 4062 ms 88148 KB Time limit exceeded
18 Halted 0 ms 0 KB -