제출 #152315

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
152315		Nucleist	늑대인간 (IOI18_werewolf)	C++14	0 / 100	4062 ms	524292 KiB

werewolf

#include <bits/stdc++.h> 
#include "werewolf.h"
using namespace std; 
#define flash ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(x) cerr << " - " << #x << ": " << x << endl;
#define debugs(x, y) cerr << " - " << #x << ": " << x << " " << #y << ": " << y << endl;
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)x.size()
#define ll long long
#define INF 1000000000
#define pb push_back
#define ve vector<ll>
#define dos pair<ll,ll>
#define vedos vector<dos>
#define rand mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
struct greateri
{
    template<class T>
    bool operator()(T const &a, T const &b) const { return a > b; }
};
vector<int>graph,rev;
vector<int>tree[200001];
int nb;
int indexi[200001],indexi1[200001];
int segtree[800001],segtree1[800001],segtree2[800001],segtree3[800001];
void dfs(int node,int p)
{
	indexi[node]=graph.size();
	indexi1[node]=nb-1-graph.size();
	graph.pb(node);
	for(auto it:tree[node]){
		if(it!=p)
			dfs(it,node);
	}
}
void build(int index,int l,int r,int yo)
{
	if(l==r)
	{
		if(!yo)
		segtree[index]=graph[l];
		else
		segtree2[index]=rev[l];
		return;
	}
	int mid =(l+r)/2;
	build(index*2,l,mid,yo);
	build(index*2+1,mid+1,r,yo);
	if(!yo)
	{
		if(segtree[index*2]<segtree[index*2+1])
			segtree[index]=segtree[index*2];
		else segtree[index]=segtree[index*2+1];
	}
	else
	{
		if(segtree2[index*2]<segtree2[index*2+1])
			segtree2[index]=segtree2[index*2];
		else segtree2[index]=segtree2[index*2+1];
	}
}
void build1(int index,int l,int r,int yo)
{
	if(l==r)
	{
		if(!yo)
		segtree1[index]=graph[l];
		else
		segtree3[index]=rev[l];
		return;
	}
	int mid =(l+r)/2;
	build1(index*2,l,mid,yo);
	build1(index*2+1,mid+1,r,yo);
	if(!yo)
	{
		if(segtree1[index*2]>segtree1[index*2+1])
			segtree1[index]=segtree1[index*2];
		else segtree1[index]=segtree1[index*2+1];
	}
	else
	{
		if(segtree3[index*2]>segtree3[index*2+1])
			segtree3[index]=segtree3[index*2];
		else segtree3[index]=segtree3[index*2+1];
	}
}
int query(int in,int l,int r,int x,int y,int val,int yo)
{
	
	if(l>y || x>r)return INF;
	else if(l>=x && r<=y)
	{
		if(!yo)
		{if(segtree[in]<val && l==r)
			return segtree[in];
		else if(segtree[in]>=val)
		return INF;}
		else
		{
		if(segtree2[in]<val && l==r)
			return segtree2[in];
		else if(segtree2[in]>=val)
		return INF;
		}
	}
	int mid = (l+r)/2;
	int fal = query(in*2,l,mid,x,y,val,yo);
	int dal = query(in*2+1,mid+1,r,x,y,val,yo);
	if(fal>=val && dal>=val)return INF;
	else if(fal>=val)return dal;
	else if(dal>=val)return fal;
	else
	{
		if(!yo)
		{if(indexi[dal]>indexi[fal])return dal;
		return fal;}
		else
		{
		if(indexi1[dal]>indexi1[fal])return dal;
		return fal;
		}
	}
}
int query1(int in,int l,int r,int x,int y,int val,int yo)
{
	//debugs(l,r);
	if(l>y || x>r)return -INF;
	else if(l>=x && r<=y && l==r)
	{
		if(!yo)
		{if(segtree1[in]>val && l==r)
			return segtree1[in];
		else if(segtree1[in]<=val)
		return -INF;}
		else if(yo)
		{
		if(segtree3[in]>val && l==r)
			return segtree3[in];
		else if(segtree3[in]<=val)
		return -INF;
		}
	}
	int mid = (l+r)/2;
	int fal = query1(in*2,l,mid,x,y,val,yo);
	int dal = query1(in*2+1,mid+1,r,x,y,val,yo);
	if(fal<=val && dal<=val)return -INF;
	else if(fal<=val)return dal;
	else if(dal<=val)return fal;
	else
	{
		if(!yo)
		{if(indexi[dal]<indexi[fal])return dal;
		return fal;}
		else
		{
		if(indexi1[dal]<indexi1[fal])return dal;
		return fal;
		}
	}
}
vector<int>check_validity(int N,vector<int>X,vector<int>Y,vector<int>S,vector<int>E,vector<int>L,vector<int>R)
{
	nb=N;
	vector<int>ans;
	ans.resize(S.size());
	for (int i = 0; i < X.size(); ++i)
	{
		int node1=X[i],node2=Y[i];
		tree[node1].pb(node2);
		tree[node2].pb(node1);
	}
	for (int i = 0; i < N; ++i)
	{
		if(tree[i].size()==1){dfs(i,-1);break;}
	}
	rev=graph;
	reverse(rev.begin(),rev.end());
	build(1,0,graph.size()-1,0);
	build(1,0,graph.size()-1,1);
	build1(1,0,graph.size()-1,0);
	build1(1,0,graph.size()-1,1);
	for (int i = 0; i < E.size(); ++i)
	{
		int hey = indexi[S[i]];
		int dey = indexi[E[i]];
		//debugs(hey,dey);
		bool ka=true;
		if(hey<dey)
		{
			int fir = query(1,0,graph.size()-1,hey,dey,L[i],0);
			//debug(fir);
			int sec = query1(1,0,graph.size()-1,hey,dey,R[i],0);
			//debugs(fir,sec);
			int ind=0,ind2=0;
			if(fir!=INF)
			ind = indexi[fir];
			if(sec!=-INF)
			ind2 = indexi[sec];
			if(fir!=INF && sec!=-INF && (ind-ind2)>=-1)ka=false;
			else if(fir!=INF && ind==dey)ka=false;
			else if(sec!=-INF && ind2==hey)ka=false;
			//debugs(ind2,hey);
			ans[i]=ka;
		}
		else
		{	
			int fir = query(1,0,graph.size()-1,nb-1-hey,nb-1-dey,L[i],1);
			int sec = query1(1,0,graph.size()-1,nb-1-hey,nb-1-dey,R[i],1);
			//debugs(fir,sec);
			int ind=0,ind2=0;
			if(fir!=INF)
			ind = indexi1[fir];
		    if(sec!=-INF)
			ind2 = indexi1[sec];
			if(fir!=INF && sec!=-INF && (ind-ind2)>=-1)ka=false;
			else if(fir!=INF && ind==(nb-1-dey))ka=false;
			else if(sec!=-INF && ind2==(nb-1-hey))ka=false;
			ans[i]=ka;
		}
	}
	return ans;
}
//code the AC sol !
// BS/queue/map

컴파일 시 표준 에러 (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:167:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < X.size(); ++i)
                  ~~^~~~~~~~~~
werewolf.cpp:183:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < E.size(); ++i)
                  ~~^~~~~~~~~~
werewolf.cpp:214:7: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
       if(sec!=-INF)
       ^~
werewolf.cpp:216:4: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
    if(fir!=INF && sec!=-INF && (ind-ind2)>=-1)ka=false;
    ^~

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