oj.uz

답안 #434135

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
434135 2021-06-20T15:29:36 Z vanic 늑대인간 (IOI18_werewolf) C++14
34 / 100
 932 ms 524292 KB 
#include "werewolf.h"
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>

using namespace std;

const int maxn=2e5+5;

struct union_find{
	int kad[maxn];
	int parent[maxn];
	int sz[maxn];
	union_find(){
		for(int i=0; i<maxn; i++){
			parent[i]=i;
			sz[i]=1;
			kad[i]=0;
		}
	}
	int find(int x, int vrij){
		if(kad[x]>vrij || parent[x]==x){
			return x;
		}
		return find(parent[x], vrij);
	}
	void update(int x, int y, int vrij){
		x=find(x, vrij);
		y=find(y, vrij);
		if(sz[x]>sz[y]){
			swap(x, y);
		}
		parent[x]=y;
		sz[y]+=sz[x];
		kad[x]=vrij;
	}
	bool query(int x, int y, int vrij){
		return find(x, vrij)==find(y, vrij);
	}
};

//int pos1[maxn], pos2[maxn];
vector < int > ms[maxn];
vector < int > s, e, l, r;
vector < int > sol;
int n;
/*
bool cmp1(int a, int b){
	return l[a]>l[b];
}

bool cmp2(int a, int b){
	return r[a]<r[b];
}
*/
union_find U1, U2;

void dodaj1(int x){
	for(int i=0; i<(int)ms[x].size(); i++){
		if(ms[x][i]<x){
			if(!U1.query(x, ms[x][i], x+1)){
				U1.update(x, ms[x][i], x+1);
			}
		}
	}
}

void dodaj2(int x){
	for(int i=0; i<(int)ms[x].size(); i++){
		if(ms[x][i]>x){
			if(!U2.query(x, ms[x][i], n-x)){
				U2.update(x, ms[x][i], n-x);
			}
		}
	}
}

vector < int > put;
int pos[maxn];

void dfs(int x, int prosl){
	put.push_back(x);
	for(int i=0; i<ms[x].size(); i++){
		if(ms[x][i]!=prosl){
			dfs(ms[x][i], x);
		}
	}
}

const int Log=18;

int binary2(int a, int pred, int vrij){
	int b;
	for(int i=Log-1; i>-1; i--){
		b=a+pred*(1<<i);
		if(b<0 || b>=n){
			continue;
		}
		if(U2.query(put[a], put[b], vrij)){
			a+=(1<<i)*pred;
		}
	}
	return a;
}

int binary1(int a, int pred, int vrij){
	int b;
	for(int i=Log-1; i>-1; i--){
		b=a+pred*(1<<i);
		if(b<0 || b>=n){
			continue;
		}
		if(U1.query(put[a], put[b], vrij)){
			a+=(1<<i)*pred;
		}
	}
	return a;
}


vector < int > check_validity(int N, vector < int > x, vector < int > y, vector < int > S, vector < int > E, vector < int > L, vector < int > R){
	s=S;
	e=E;
	l=L;
	r=R;
	n=N;
	int m=x.size();
	for(int i=0; i<m; i++){
		ms[x[i]].push_back(y[i]);
		ms[y[i]].push_back(x[i]);
	}
	int q=s.size();
	for(int i=0; i<n; i++){
		dodaj1(i);
		dodaj2(n-i-1);
	}
	int poc;
	for(int i=0; i<n; i++){
		if(ms[i].size()==1){
			poc=i;
			break;
		}
	}
	dfs(poc, poc);
	for(int i=0; i<n; i++){
		pos[put[i]]=i;
	}
	int a, b;
	for(int i=0; i<q; i++){
		if(pos[s[i]]<pos[e[i]]){
			a=binary2(pos[s[i]], 1, n-l[i]);
			b=binary1(pos[e[i]], -1, r[i]+1);
			if(a>=b){
				sol.push_back(1);
			}
			else{
				sol.push_back(0);
			}
		}
		else{
			a=binary2(pos[s[i]], -1, n-l[i]);
			b=binary1(pos[e[i]], 1, r[i]+1);
			if(a<=b){
				sol.push_back(1);
			}
			else{
				sol.push_back(0);
			}
		}
//		cout << a << ' ' << b << endl;
	}
	return sol;
}

Compilation message

werewolf.cpp: In function 'void dfs(int, int)':
werewolf.cpp:84:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |  for(int i=0; i<ms[x].size(); i++){
      |               ~^~~~~~~~~~~~~
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:145:5: warning: 'poc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  145 |  dfs(poc, poc);
      |  ~~~^~~~~~~~~~

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 383 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 383 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 767 ms 41128 KB Output is correct
2 Correct 622 ms 41144 KB Output is correct
3 Correct 622 ms 49556 KB Output is correct
4 Correct 779 ms 49556 KB Output is correct
5 Correct 862 ms 49620 KB Output is correct
6 Correct 776 ms 49516 KB Output is correct
7 Correct 914 ms 49576 KB Output is correct
8 Correct 539 ms 49464 KB Output is correct
9 Correct 470 ms 49512 KB Output is correct
10 Correct 626 ms 49492 KB Output is correct
11 Correct 614 ms 49560 KB Output is correct
12 Correct 573 ms 49568 KB Output is correct
13 Correct 560 ms 49492 KB Output is correct
14 Correct 583 ms 49720 KB Output is correct
15 Correct 522 ms 49496 KB Output is correct
16 Correct 541 ms 49524 KB Output is correct
17 Correct 932 ms 49512 KB Output is correct

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 383 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -