oj.uz

Submission #421479

# Submission time Handle Problem Language Result Execution time Memory
421479 2021-06-09T08:00:59 Z alireza_kaviani Werewolf (IOI18_werewolf) C++11
100 / 100
 1032 ms 196008 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

const int MAXN = 4e5 + 10;

int nodeInd , timer , par[MAXN] , sz[MAXN] , root[MAXN] , subtree[MAXN] , st[MAXN] , fn[MAXN] , l[MAXN] , r[MAXN];
vector<int> ans , G[2][MAXN] , adj[MAXN] , Q[2][MAXN] , vec[MAXN];
set<int> sub[MAXN];

void clear(int n){
	fill(par , par + MAXN , -1);
	fill(sz , sz + MAXN , 1);
	fill(adj , adj + MAXN , vector<int>());
	fill(subtree , subtree + MAXN , 0);
	for(int i = 0 ; i < MAXN ; i++)	root[i] = i;
	nodeInd = n;
}

int Find(int v){
	return (par[v] == -1 ? v : par[v] = Find(par[v]));
}

void Union(int v , int u){
	v = Find(v); u = Find(u);
	if(v == u)	return;
	if(sz[v] < sz[u])	swap(v , u);
	par[u] = v; sz[v] += sz[u];
	adj[nodeInd].push_back(root[v]);
	adj[nodeInd].push_back(root[u]);
	root[v] = nodeInd++;
}

void PreDFS(int v){
	st[v] = ++timer;
	for(int u : adj[v]){
		PreDFS(u);
	}
	fn[v] = timer;
}

void SolveDFS(int v){
	int leaf = 1;
	for(int u : adj[v]){
		leaf = 0;
		SolveDFS(u);
		if(sub[v].size() < sub[u].size()){
			sub[v].swap(sub[u]);
		}
		for(auto &i : sub[u])	sub[v].insert(i);
	}
	if(leaf)	sub[v].insert(st[v]);
	for(int i : vec[v]){
		auto it = sub[v].lower_bound(l[i]);
		if(it == sub[v].end() || (*it) > r[i])	ans[i] = 0;
	}
}

vector<int> check_validity(int n, vector<int> X, vector<int> Y,
                                  vector<int> S, vector<int> E,
                                  vector<int> L, vector<int> R) {
	int m = X.size() , q = S.size();
	ans = vector<int>(q , 1);
	for(int i = 0 ; i < m ; i++){
		int v = X[i] , u = Y[i];
		if(v > u)	swap(v , u);
		G[0][v].push_back(u);
		G[1][u].push_back(v);
	}
	for(int i = 0 ; i < q ; i++){
		Q[0][L[i]].push_back(i);
		Q[1][R[i]].push_back(i);
	}
	clear(n);
	for(int i = n - 1 ; i >= 0 ; i--){
		for(int j : G[0][i]){
			Union(i , j);
		}
		for(int j : Q[0][i]){
			if(S[j] < i)	ans[j] = 0;
			subtree[j] = root[Find(S[j])];
		}
	}
	PreDFS(nodeInd - 1);
	for(int i = 0 ; i < q ; i++){
		l[i] = st[subtree[i]];
		r[i] = fn[subtree[i]];
	}
	clear(n);
	for(int i = 0 ; i < n ; i++){
		for(int j : G[1][i]){
			Union(i , j);
		}
		for(int j : Q[1][i]){
			if(E[j] > i)	ans[j] = 0;
			subtree[j] = root[Find(E[j])];
			vec[subtree[j]].push_back(j);
		}
	}
	SolveDFS(nodeInd - 1);
	return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 81736 KB Output is correct
2 Correct 56 ms 81632 KB Output is correct
3 Correct 50 ms 81680 KB Output is correct
4 Correct 48 ms 81600 KB Output is correct
5 Correct 61 ms 81640 KB Output is correct
6 Correct 51 ms 81700 KB Output is correct
7 Correct 53 ms 81668 KB Output is correct
8 Correct 55 ms 81716 KB Output is correct
9 Correct 56 ms 81664 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 81736 KB Output is correct
2 Correct 56 ms 81632 KB Output is correct
3 Correct 50 ms 81680 KB Output is correct
4 Correct 48 ms 81600 KB Output is correct
5 Correct 61 ms 81640 KB Output is correct
6 Correct 51 ms 81700 KB Output is correct
7 Correct 53 ms 81668 KB Output is correct
8 Correct 55 ms 81716 KB Output is correct
9 Correct 56 ms 81664 KB Output is correct
10 Correct 59 ms 82824 KB Output is correct
11 Correct 59 ms 82892 KB Output is correct
12 Correct 61 ms 83048 KB Output is correct
13 Correct 68 ms 83008 KB Output is correct
14 Correct 60 ms 82932 KB Output is correct
15 Correct 60 ms 82968 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1032 ms 196008 KB Output is correct
2 Correct 643 ms 161772 KB Output is correct
3 Correct 695 ms 160824 KB Output is correct
4 Correct 834 ms 166244 KB Output is correct
5 Correct 834 ms 167536 KB Output is correct
6 Correct 919 ms 174496 KB Output is correct
7 Correct 1010 ms 194080 KB Output is correct
8 Correct 688 ms 161648 KB Output is correct
9 Correct 744 ms 159556 KB Output is correct
10 Correct 739 ms 164408 KB Output is correct
11 Correct 676 ms 166100 KB Output is correct
12 Correct 827 ms 173776 KB Output is correct
13 Correct 695 ms 166564 KB Output is correct
14 Correct 692 ms 166536 KB Output is correct
15 Correct 687 ms 166596 KB Output is correct
16 Correct 691 ms 166668 KB Output is correct
17 Correct 976 ms 193348 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 81736 KB Output is correct
2 Correct 56 ms 81632 KB Output is correct
3 Correct 50 ms 81680 KB Output is correct
4 Correct 48 ms 81600 KB Output is correct
5 Correct 61 ms 81640 KB Output is correct
6 Correct 51 ms 81700 KB Output is correct
7 Correct 53 ms 81668 KB Output is correct
8 Correct 55 ms 81716 KB Output is correct
9 Correct 56 ms 81664 KB Output is correct
10 Correct 59 ms 82824 KB Output is correct
11 Correct 59 ms 82892 KB Output is correct
12 Correct 61 ms 83048 KB Output is correct
13 Correct 68 ms 83008 KB Output is correct
14 Correct 60 ms 82932 KB Output is correct
15 Correct 60 ms 82968 KB Output is correct
16 Correct 1032 ms 196008 KB Output is correct
17 Correct 643 ms 161772 KB Output is correct
18 Correct 695 ms 160824 KB Output is correct
19 Correct 834 ms 166244 KB Output is correct
20 Correct 834 ms 167536 KB Output is correct
21 Correct 919 ms 174496 KB Output is correct
22 Correct 1010 ms 194080 KB Output is correct
23 Correct 688 ms 161648 KB Output is correct
24 Correct 744 ms 159556 KB Output is correct
25 Correct 739 ms 164408 KB Output is correct
26 Correct 676 ms 166100 KB Output is correct
27 Correct 827 ms 173776 KB Output is correct
28 Correct 695 ms 166564 KB Output is correct
29 Correct 692 ms 166536 KB Output is correct
30 Correct 687 ms 166596 KB Output is correct
31 Correct 691 ms 166668 KB Output is correct
32 Correct 976 ms 193348 KB Output is correct
33 Correct 936 ms 166804 KB Output is correct
34 Correct 360 ms 117032 KB Output is correct
35 Correct 902 ms 164356 KB Output is correct
36 Correct 940 ms 169560 KB Output is correct
37 Correct 934 ms 163752 KB Output is correct
38 Correct 953 ms 167296 KB Output is correct
39 Correct 859 ms 168552 KB Output is correct
40 Correct 888 ms 167864 KB Output is correct
41 Correct 845 ms 162216 KB Output is correct
42 Correct 861 ms 166072 KB Output is correct
43 Correct 878 ms 168516 KB Output is correct
44 Correct 864 ms 162816 KB Output is correct
45 Correct 696 ms 168592 KB Output is correct
46 Correct 763 ms 168356 KB Output is correct
47 Correct 723 ms 166724 KB Output is correct
48 Correct 705 ms 166676 KB Output is correct
49 Correct 719 ms 166864 KB Output is correct
50 Correct 727 ms 166728 KB Output is correct
51 Correct 866 ms 165068 KB Output is correct
52 Correct 844 ms 165128 KB Output is correct