제출 #1008818

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1008818		NintsiChkhaidze	늑대인간 (IOI18_werewolf)	C++17	100 / 100	703 ms	156216 KiB

werewolf

#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;
}

컴파일 시 표준 에러 (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: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 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 51 / 51