제출 #379335

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
379335		autumn_eel	늑대인간 (IOI18_werewolf)	C++14	49 / 100	1766 ms	36708 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;

const int INF=0x3f3f3f3f;

struct UnionFind{
	vector<int>par;
	UnionFind(int n){
		par=vector<int>(n);
		rep(i,n)par[i]=i;
	}
	int find(int x){
		return par[x]==x?x:par[x]=find(par[x]);
	}
	void unite(int x,int y){
		x=find(x);y=find(y);
		par[y]=x;
	}
	bool same(int x,int y){
		return find(x)==find(y);
	}
};

struct Segtree{
	int N;
	vector<int>dat;
	function<int(int,int)>f;
	int ini;

	Segtree(int n,int ini,function<int(int,int)>f):ini(ini),f(f){
		N=1;while(N<n)N<<=1;
		dat=vector<int>(2*N,ini);
	}

	void update(int k,int x){
		k+=N;dat[k]=x;
		while(k>1){
			k>>=1;
			dat[k]=f(dat[k*2],dat[k*2+1]);
		}
	}

	int query(int l,int r){
		int res=ini;
		for(l+=N,r+=N;l<r;l>>=1,r>>=1){
			if(l&1)res=f(res,dat[l++]);
			if(r&1)res=f(res,dat[--r]);
		}
		return res;
	}

};
vector<int>G[300000];
int pos[300000];

std::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 M=X.size();
	int Q=S.size();
	if(N<=3000&&M<=6000&&Q<=3000){
		vector<int>ans;
		rep(i,Q){
			UnionFind uf1(N),uf2(N);
			rep(j,M){
				if(X[j]>=L[i]&&Y[j]>=L[i])uf1.unite(X[j],Y[j]);
				if(X[j]<=R[i]&&Y[j]<=R[i])uf2.unite(X[j],Y[j]);
			}
			bool ok=false;
			rep(j,N){
				if(uf1.same(S[i],j)&&uf2.same(E[i],j)){
					ok=true;break;
				}
			}
			ans.push_back(ok);
		}
		return ans;
	}
	rep(i,M){
		G[X[i]].push_back(Y[i]);
		G[Y[i]].push_back(X[i]);
	}
	int s=-1;
	rep(i,N){
		if(G[i].size()==1){
			s=i;break;
		}
	}
	vector<int>vs;
	memset(pos,-1,sizeof(pos));
	rep(i,N){
		vs.push_back(s);
		pos[s]=i;
		for(int u:G[s]){
			if(pos[u]==-1){
				s=u;
			}
		}
	}
	Segtree seg1(N,INF,[](int a,int b){return min(a,b);});
	Segtree seg2(N,0,[](int a,int b){return max(a,b);});
	rep(i,N){
		seg1.update(i,vs[i]);
		seg2.update(i,vs[i]);
	}
	vector<int>ans;
	rep(i,Q){
		int s=pos[S[i]],e=pos[E[i]];
		if(s<e){
			int ok1=s,ng1=N;
			while(ng1-ok1>1){
				int t=(ok1+ng1)/2;
				if(seg1.query(s,t+1)>=L[i])ok1=t;
				else ng1=t;
			}
			int ok2=e,ng2=-1;
			while(ok2-ng2>1){
				int t=(ok2+ng2)/2;
				if(seg2.query(t,e+1)<=R[i])ok2=t;
				else ng2=t;
			}
			ans.push_back(ok2<=ok1);
		}
		else{
			int ok1=s,ng1=-1;
			while(ok1-ng1>1){
				int t=(ok1+ng1)/2;
				if(seg1.query(t,s+1)>=L[i])ok1=t;
				else ng1=t;
			}
			int ok2=e,ng2=N;
			while(ng2-ok2>1){
				int t=(ok2+ng2)/2;
				if(seg2.query(e,t+1)<=R[i])ok2=t;
				else ng2=t;
			}
			ans.push_back(ok1<=ok2);
		}
	}
	return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

werewolf.cpp: In constructor 'Segtree::Segtree(int, int, std::function<int(int, int)>)':
werewolf.cpp:30:6: warning: 'Segtree::ini' will be initialized after [-Wreorder]
   30 |  int ini;
      |      ^~~
werewolf.cpp:29:24: warning:   'std::function<int(int, int)> Segtree::f' [-Wreorder]
   29 |  function<int(int,int)>f;
      |                        ^
werewolf.cpp:32:2: warning:   when initialized here [-Wreorder]
   32 |  Segtree(int n,int ini,function<int(int,int)>f):ini(ini),f(f){
      |  ^~~~~~~

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