oj.uz

Submission #1008818

# Submission time Handle Problem Language Result Execution time Memory
1008818 2024-06-26T20:33:43 Z NintsiChkhaidze Werewolf (IOI18_werewolf) C++17
100 / 100
 703 ms 156216 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
#define pb push_back
#define left h*2,l,(l + r)/2
#define right h*2+1,(l+r)/2 + 1,r
using namespace std;
 
const int NN = 2e5 + 3;
vector <int> v[NN],g[4][NN],t[4*NN];
int p[NN],par[4][NN],d[5][25][NN],timer;
int tin[4][NN],tout[4][NN],rev[4][NN];
bool active[NN],fix[NN];
 
int P(int x){
	if (x==p[x]) return x;
	return p[x]=P(p[x]);
}
 
void dsu(int id,int x,int y){
	if (P(x) == P(y)) return;
	y = P(y);
	par[id][y] = x;
	g[id][x].pb(y);
//	cout<<"Edge "<<y<<" -> "<<x<<endl;
	p[y] = x;
}
 
void dfs(int id,int x,int par){
	d[id][0][x] = par;
//	cout<<"> "<<id<<" "<<x<<endl;
	tin[id][x] = ++timer;
	rev[id][timer] = x;
	for (int to: g[id][x]){
		if (to != par) dfs(id,to,x);
	}
	tout[id][x] = timer;
}

vector <int> merge(vector <int> x,vector <int> y){
	for (int yy: y)
		x.pb(yy);
	sort(x.begin(),x.end());
	return x;
}


void build(int h,int l,int r){
	if (l == r){
		t[h].pb( tin[2][rev[1][l]]);
		return;
	}
	
	build(left);
	build(right);
	t[h] = merge(t[h*2],t[h*2+1]);
}


int get(int h,int l,int r,int L,int R,int le,int ri){
	if (r < L || R < l) return 0;
	if (L <= l && r <= R){
		int l1=0,r1=t[h].size()-1,res=-1;
		while (l1 <= r1){
			int mid = (l1+r1)>>1;
			if (t[h][mid] >= le){
				res=t[h][mid];
				r1=mid-1;
			}else{
				l1=mid+1;
			}
		}
		
		return (res >= le && res <= ri);
	}
	
	if (get(left,L,R,le,ri)) return 1;
	return get(right,L,R,le,ri);
}


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 Q = S.size(),n = N;
  vector<int> ans(Q);
	
  for (int i=0;i<X.size();i++){
  	v[X[i]].pb(Y[i]);
  	v[Y[i]].pb(X[i]);
  }
  
  for (int i=0;i<n;i++)
  	p[i] = i,par[1][i] = par[2][i] = -1;
  	
  for (int i = 0; i < n; i++){
  	active[i] = 1;
  	
  	for (int to: v[i]){
  		if (active[to]) dsu(1,i,to);
	  }
  }
  
  for (int i=0;i<n;i++)
  	p[i] = i,par[1][i] = par[2][i] = -1,active[i] = 0;
  	
  for (int i = n-1; i >= 0; i--){
  	active[i] = 1;
  	
  	for (int to: v[i]){
  		if (active[to]) dsu(2,i,to);
	  }
  }
  
  int root1,root2;
  for (int i=0;i<n;i++){
  	if (par[1][i] == -1) root1 = i;
  	if (par[2][i] == -1) root2 = i;
  }
  
  timer=0; dfs(1,root1,root1);
  timer=0; dfs(2,root2,root2);
  	
	build(1,1,n);
  for (int j = 1; j < 20; j++){
  	for (int i=0;i<n;i++){
  		d[1][j][i] = d[1][j - 1][d[1][j - 1][i]];
  		d[2][j][i] = d[2][j - 1][d[2][j - 1][i]];
	  }
  }
  
  for (int i = 0; i < Q; i++){
  	int A = S[i],B = E[i],l = L[i],r = R[i];
	
	for (int j = 19; j >= 0; j--) {
		if (d[1][j][B] <= r) B = d[1][j][B];
		if (d[2][j][A] >= l) A = d[2][j][A];
	}
	
	if (A < l || B > r) continue;
	
	int l1 = tin[1][B],r1 = tout[1][B];
	int l2 = tin[2][A],r2 = tout[2][A];
	ans[i] = get(1,1,n,l1,r1,l2,r2);
  }
  return ans;
}

Compilation message

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:87:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |   for (int i=0;i<X.size();i++){
      |                ~^~~~~~~~~
werewolf.cpp:121:15: warning: 'root2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  121 |   timer=0; dfs(2,root2,root2);
      |            ~~~^~~~~~~~~~~~~~~
werewolf.cpp:120:15: warning: 'root1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  120 |   timer=0; dfs(1,root1,root1);
      |            ~~~^~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 42840 KB Output is correct
2 Correct 18 ms 42844 KB Output is correct
3 Correct 17 ms 42872 KB Output is correct
4 Correct 18 ms 42840 KB Output is correct
5 Correct 20 ms 42840 KB Output is correct
6 Correct 19 ms 42844 KB Output is correct
7 Correct 20 ms 42844 KB Output is correct
8 Correct 19 ms 42844 KB Output is correct
9 Correct 22 ms 42844 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 42840 KB Output is correct
2 Correct 18 ms 42844 KB Output is correct
3 Correct 17 ms 42872 KB Output is correct
4 Correct 18 ms 42840 KB Output is correct
5 Correct 20 ms 42840 KB Output is correct
6 Correct 19 ms 42844 KB Output is correct
7 Correct 20 ms 42844 KB Output is correct
8 Correct 19 ms 42844 KB Output is correct
9 Correct 22 ms 42844 KB Output is correct
10 Correct 21 ms 44376 KB Output is correct
11 Correct 21 ms 44372 KB Output is correct
12 Correct 21 ms 44380 KB Output is correct
13 Correct 23 ms 44636 KB Output is correct
14 Correct 20 ms 44432 KB Output is correct
15 Correct 27 ms 44376 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 503 ms 137936 KB Output is correct
2 Correct 499 ms 143860 KB Output is correct
3 Correct 441 ms 140596 KB Output is correct
4 Correct 479 ms 139056 KB Output is correct
5 Correct 477 ms 139156 KB Output is correct
6 Correct 511 ms 138804 KB Output is correct
7 Correct 501 ms 138800 KB Output is correct
8 Correct 476 ms 144436 KB Output is correct
9 Correct 375 ms 140596 KB Output is correct
10 Correct 333 ms 139136 KB Output is correct
11 Correct 395 ms 139064 KB Output is correct
12 Correct 394 ms 138804 KB Output is correct
13 Correct 571 ms 150792 KB Output is correct
14 Correct 514 ms 150824 KB Output is correct
15 Correct 496 ms 150812 KB Output is correct
16 Correct 519 ms 150676 KB Output is correct
17 Correct 451 ms 138760 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 42840 KB Output is correct
2 Correct 18 ms 42844 KB Output is correct
3 Correct 17 ms 42872 KB Output is correct
4 Correct 18 ms 42840 KB Output is correct
5 Correct 20 ms 42840 KB Output is correct
6 Correct 19 ms 42844 KB Output is correct
7 Correct 20 ms 42844 KB Output is correct
8 Correct 19 ms 42844 KB Output is correct
9 Correct 22 ms 42844 KB Output is correct
10 Correct 21 ms 44376 KB Output is correct
11 Correct 21 ms 44372 KB Output is correct
12 Correct 21 ms 44380 KB Output is correct
13 Correct 23 ms 44636 KB Output is correct
14 Correct 20 ms 44432 KB Output is correct
15 Correct 27 ms 44376 KB Output is correct
16 Correct 503 ms 137936 KB Output is correct
17 Correct 499 ms 143860 KB Output is correct
18 Correct 441 ms 140596 KB Output is correct
19 Correct 479 ms 139056 KB Output is correct
20 Correct 477 ms 139156 KB Output is correct
21 Correct 511 ms 138804 KB Output is correct
22 Correct 501 ms 138800 KB Output is correct
23 Correct 476 ms 144436 KB Output is correct
24 Correct 375 ms 140596 KB Output is correct
25 Correct 333 ms 139136 KB Output is correct
26 Correct 395 ms 139064 KB Output is correct
27 Correct 394 ms 138804 KB Output is correct
28 Correct 571 ms 150792 KB Output is correct
29 Correct 514 ms 150824 KB Output is correct
30 Correct 496 ms 150812 KB Output is correct
31 Correct 519 ms 150676 KB Output is correct
32 Correct 451 ms 138760 KB Output is correct
33 Correct 570 ms 139784 KB Output is correct
34 Correct 190 ms 74580 KB Output is correct
35 Correct 580 ms 143788 KB Output is correct
36 Correct 562 ms 139716 KB Output is correct
37 Correct 648 ms 142640 KB Output is correct
38 Correct 616 ms 140660 KB Output is correct
39 Correct 703 ms 155900 KB Output is correct
40 Correct 577 ms 150836 KB Output is correct
41 Correct 473 ms 141612 KB Output is correct
42 Correct 381 ms 139828 KB Output is correct
43 Correct 542 ms 149880 KB Output is correct
44 Correct 476 ms 142640 KB Output is correct
45 Correct 526 ms 156216 KB Output is correct
46 Correct 490 ms 155700 KB Output is correct
47 Correct 471 ms 150792 KB Output is correct
48 Correct 510 ms 150804 KB Output is correct
49 Correct 520 ms 150836 KB Output is correct
50 Correct 506 ms 150832 KB Output is correct
51 Correct 537 ms 150836 KB Output is correct
52 Correct 519 ms 150856 KB Output is correct