Submission #1008801

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008801		NintsiChkhaidze	Werewolf (IOI18_werewolf)	C++17	0 / 100	858 ms	96076 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;

const int NN = 2e5 + 3;
vector <int> v[NN],g[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;
	par[id][P(y)] = x;
	g[id][x].pb(P(y));
	p[P(y)] = x;
}

void dfs(int id,int x,int par){
	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> 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++){
  	d[1][0][i] = par[1][i];
  	d[2][0][i] = par[2][i];
  	if (par[1][i] == -1) d[1][0][i] = i,root1 = i;
  	if (par[2][i] == -1) d[2][0][i] = i,root2 = i;
  }
  
  timer=0; dfs(1,root1,root1);
  timer=0; dfs(2,root2,root2);
  
  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];
	for (int j=0;j<n;j++) fix[j] = 0;
	for (int j = l1; j <= r1; j++){
		fix[rev[1][j]] = 1;
	}
	int l2 = tin[2][A],r2 = tout[2][A];
	for (int j = l2; j <= r2; j++){
		if (fix[rev[2][j]]) ans[i] = 1;
	}
  }
  return ans;
}

Compilation message (stderr)

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

• Subtask 1: 0 / 7
• Subtask 2: 0 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51