oj.uz

답안 #88842

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
88842 2018-12-09T08:12:21 Z dsjong 늑대인간 (IOI18_werewolf) C++14
15 / 100
 1424 ms 140980 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
vector<int>adj1[3005];
vector<int>adj2[3005];
vector<int>adj3[200001];
bool b=false;
bool vis1[3005];
bool vis2[3005];
bool vis3[200001];
int cnt[200001];
vector<int>v;
int rv[200001];
int st1[200001][19];
int st2[200001][19];
void dfs1(int cur,int par){
	vis1[cur]=1;
	for(int i:adj1[cur]){
		if(i!=par&&!vis1[i]){
			dfs1(i,cur);
		}
	}
}
void dfs2(int cur,int par){
	vis2[cur]=1;
	if(vis1[cur]){
		b=true;
		return;
	}
	for(int i:adj2[cur]){
		if(i!=par&&!vis2[i]){
			dfs2(i,cur);
		}
	}
}
void dfs3(int cur,int par){
	vis3[cur]=1;
	for(int i:adj3[cur]){
		if(i!=par&&!vis3[i]){
			v.push_back(i);
			rv[i]=v.size()-1;
			dfs3(i,cur);
		}
	}
}
void build1(int N){
	for(int i=0;i<N;i++){
		st1[i][0]=i;
	}
	for(int j=1;j<=(int)log2(N);j++){
		for(int i=0;i<N+1-(1<<j);i++){
			if(v[st1[i][j-1]]<v[st1[i+(1<<(j-1))][j-1]]){
				st1[i][j]=st1[i][j-1];
			}
			else{
				st1[i][j]=st1[i+(1<<(j-1))][j-1];
			}
		}
	}
}
void build2(int N){
	for(int i=0;i<N;i++){
		st2[i][0]=i;
	}
	for(int j=1;j<=(int)log2(N);j++){
		for(int i=0;i<N+1-(1<<j);i++){
			if(v[st2[i][j-1]]>v[st2[i+(1<<(j-1))][j-1]]){
				st2[i][j]=st2[i][j-1];
			}
			else{
				st2[i][j]=st2[i+(1<<(j-1))][j-1];
			}
		}
	}
}
int query1(int L,int R){
	int j=(int)log2(R-L+1);
	if(v[st1[L][j]]<v[st1[R-(1<<j)+1][j]]){
		return st1[L][j];
	}
	return st1[R-(1<<j)+1][j];
}
int query2(int L,int R){
	int j=(int)log2(R-L+1);
	if(v[st2[L][j]]>v[st2[R-(1<<j)+1][j]]){
		return st2[L][j];
	}
	return st2[R-(1<<j)+1][j];
}
int bsearch1(int s,int e,int l,bool b){
	if(v[query1(s,e)]>=l){
		if(b) return e+1;
		return e-1;
	}
	if(b){
		//search from left
		int m=(s+e)/2;
		if(e-s<=1){
			if(v[s]<l){
				return s;
			}
			return e;
		}
		if(v[query1(s,m)]<l){
			return bsearch1(s,m,l,b);
		}
		return bsearch1(m,e,l,b);
	}
	else{
		//search from right
		int m=(s+e)/2;
		if(s-e<=1){
			if(v[s]<l){
				return s;
			}
			return e;
		}
		if(v[query1(m,s)]<l){
			return bsearch1(m,s,l,b);
		}
		return bsearch1(e,m,l,b);
	}
}
int bsearch2(int s,int e,int r,bool b){
	if(v[query2(s,e)]<=r){
		if(b) return s-1;
		return s+1;
	}
	if(b){
		//search from right
		int m=(s+e)/2;
		if(e-s<=1){
			if(v[e]>r){
				return e;
			}
			return s;
		}
		if(v[query2(m,e)]>r){
			return bsearch2(m,e,r,b);
		}
		return bsearch2(s,m,r,b);
	}
	else{
		//search from left
		int m=(s+e)/2;
		if(s-e<=1){
			if(v[e]>r){
				return e;
			}
			return s;
		}
		if(v[query2(e,m)]>r){
			return bsearch2(e,m,r,b);
		}
		return bsearch2(m,s,r,b);
	}
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y,
                                vector<int> S, vector<int> E,
                                vector<int> L, vector<int> R) {
	vector<int>ans;
	if(N<=3000){
		for(int i=0;i<L.size();i++){
			memset(vis1,0,sizeof vis1);
			memset(vis2,0,sizeof vis2);
			int l=L[i],r=R[i],s=S[i],e=E[i];
			for(int j=0;j<=3000;j++){
				adj1[j].clear();
				adj2[j].clear();
			}
			for(int j=0;j<X.size();j++){
				if(X[j]>=l&&Y[j]>=l){
					adj1[X[j]].push_back(Y[j]);
					adj1[Y[j]].push_back(X[j]);
				}
				if(X[j]<=r&&Y[j]<=r){
					adj2[X[j]].push_back(Y[j]);
					adj2[Y[j]].push_back(X[j]);
				}
			}
			b=false;
			dfs1(s,3003);
			dfs2(e,3003);
			if(b){
				ans.push_back(1);
			}
			else{
				ans.push_back(0);
			}
		}
	}
	else{
		for(int i=0;i<X.size();i++){
			cnt[X[i]]++;
			cnt[Y[i]]++;
			adj3[X[i]].push_back(Y[i]);
			adj3[Y[i]].push_back(X[i]);
		}
		for(int i=0;i<N;i++){
			if(cnt[i]==1){
				v.push_back(i);
				rv[i]=0;
				break;
			}
		}
		dfs3(v[0],200005);
		build1(N);
		build2(N);
		for(int i=0;i<S.size();i++){
			int s=rv[S[i]],e=rv[E[i]],l=L[i],r=R[i];
			bool b=false;
			if(s<e){
				b=true;
			}
			int x=bsearch1(s,e,l,b);
			int y=bsearch2(s,e,r,b);
			if(b){
				x--;
				y++;
			}
			else{
				x++;
				y--;
			}
			if(b^(x>=y)){
				ans.push_back(0);
			}
			else{
				ans.push_back(1);
			}
		}
	}
	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:163:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<L.size();i++){
               ~^~~~~~~~~
werewolf.cpp:171:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0;j<X.size();j++){
                ~^~~~~~~~~
werewolf.cpp:193:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<X.size();i++){
               ~^~~~~~~~~
werewolf.cpp:209:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<S.size();i++){
               ~^~~~~~~~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 5240 KB Output is correct
2 Correct 7 ms 5252 KB Output is correct
3 Correct 9 ms 5316 KB Output is correct
4 Correct 9 ms 5316 KB Output is correct
5 Correct 8 ms 5392 KB Output is correct
6 Correct 8 ms 5396 KB Output is correct
7 Correct 8 ms 5416 KB Output is correct
8 Correct 8 ms 5416 KB Output is correct
9 Correct 8 ms 5416 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 5240 KB Output is correct
2 Correct 7 ms 5252 KB Output is correct
3 Correct 9 ms 5316 KB Output is correct
4 Correct 9 ms 5316 KB Output is correct
5 Correct 8 ms 5392 KB Output is correct
6 Correct 8 ms 5396 KB Output is correct
7 Correct 8 ms 5416 KB Output is correct
8 Correct 8 ms 5416 KB Output is correct
9 Correct 8 ms 5416 KB Output is correct
10 Correct 574 ms 5984 KB Output is correct
11 Correct 450 ms 6164 KB Output is correct
12 Correct 382 ms 6432 KB Output is correct
13 Correct 671 ms 6552 KB Output is correct
14 Correct 528 ms 6552 KB Output is correct
15 Correct 1424 ms 6984 KB Output is correct

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 490 ms 140980 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 5240 KB Output is correct
2 Correct 7 ms 5252 KB Output is correct
3 Correct 9 ms 5316 KB Output is correct
4 Correct 9 ms 5316 KB Output is correct
5 Correct 8 ms 5392 KB Output is correct
6 Correct 8 ms 5396 KB Output is correct
7 Correct 8 ms 5416 KB Output is correct
8 Correct 8 ms 5416 KB Output is correct
9 Correct 8 ms 5416 KB Output is correct
10 Correct 574 ms 5984 KB Output is correct
11 Correct 450 ms 6164 KB Output is correct
12 Correct 382 ms 6432 KB Output is correct
13 Correct 671 ms 6552 KB Output is correct
14 Correct 528 ms 6552 KB Output is correct
15 Correct 1424 ms 6984 KB Output is correct
16 Runtime error 490 ms 140980 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Halted 0 ms 0 KB -