Submission #954775

#	Time	Username	Problem	Language	Result	Execution time	Memory
954775		djs100201	Werewolf (IOI18_werewolf)	C++17	0 / 100	347 ms	268292 KiB

werewolf

#include<bits/stdc++.h>
#include<werewolf.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
#define all(v) v.begin(),v.end()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
using PP = pair<ll, P>;
const ll n_ =4e5+100, inf = (ll)2e9 * (ll)1e9 + 7, mod = 1e9+7;
ll n, m, tc = 1, a, b, c, d, sum, x, y, z, base, ans, k;
ll gcd(ll x,ll y){
	if(!y)return x;
	return gcd(y,x%y);
}
//ctrl + g ->줄이동

class seg{
	public:
	vector<ll>tree;
	ll base;
	seg(int n){
		for(base=1;base<=n;base*=2);
		//0~n쓰겠다
		tree.resize(n*4+4,-inf);
	}
	ll f(ll l,ll r){
		l+=base,r+=base;
		ll ret=-inf;
		while(l<=r){
			if(l%2)ret=max(ret,tree[l++]);
			if(!(r%2))ret=max(ret,tree[r--]);
			l/=2,r/=2;
		}
		return ret;
	}
	void update(ll i,ll v){
		i+=base;
		tree[i]=max(tree[i],v);
		i/=2;
		while(i){
			tree[i]=max(tree[i*2],tree[i*2+1]);
			i/=2;
		}
	}
};
class UF{
	public:
	vector<int>par;
	UF(int n){
		par.resize(n+1);
		for(int i=0;i<=n;i++)par[i]=-1;
	}
	int find(int x){
		if(par[x]!=-1)return x;
		return par[x]=find(par[x]);
	}
	void merge(int x,int y){
		x=find(x),y=find(y);
		if(x==y)return;
		par[x]=y;
	}
};
class graph{
	public:
	vector<vector<ll>>edge;
	vector<ll>in,out;
	int cnt;
	graph(int n){
		edge.resize(n+1);
		in.resize(n+1);
		out.resize(n+1);
		cnt=0;
	}
	void add_edge(int u,int v){
		edge[u].push_back(v);
		edge[v].push_back(u);
	}
	void dfs(ll x,ll par){
		in[x]=cnt++;
		for(auto nxt:edge[x]){
			if(nxt==par)continue;
			dfs(nxt,x);
		}
		out[x]=cnt;
	}
};
vector<ll>v1[n_],v2[n_],LQ[n_],RQ[n_],XX[n_],XQ[n_];
ll Lidx[n_],Ridx[n_];
vector<P>YQ[n_];
vector<int>check_validity(int N,vector<int>X,vector<int>Y,vector<int>S,vector<int>E,vector<int>L,vector<int>R){
	n=N;
	ll q=L.size();
	vector<int>ret(q);
	for(int i=0;i<q;i++){
		LQ[L[i]].push_back(i);
		RQ[R[i]].push_back(i);
	}
	for(int i=0;i<X.size();i++){
		if(X[i]>Y[i])swap(X[i],Y[i]);
		v1[X[i]].push_back(Y[i]);
		v2[Y[i]].push_back(X[i]);
	}
	
	UF LL(2*n),RR(2*n);
	graph LG(2*n),RG(2*n);

	base=n+1;
	for(int i=n-1;i>=0;i--){
		for(auto nxt:v1[i]){
			if(LL.find(i)==LL.find(nxt))continue;
			LG.add_edge(i,base),LG.add_edge(nxt,base);
			LL.merge(i,base),LL.merge(nxt,base);
			base++;
		}
		for(auto nxt:LQ[i])Lidx[nxt]=LL.find(S[nxt]);
	}
	LG.dfs(base-1,0);

	base=n+1;
	for(int i=0;i<n;i++){
		for(auto nxt:v2[i]){
			if(RR.find(i)==RR.find(nxt))continue;
			RG.add_edge(i,base),RG.add_edge(nxt,base);
			RR.merge(i,base),RR.merge(nxt,base);
			base++;
		}
		for(auto nxt:RQ[i])Ridx[nxt]=RR.find(E[nxt]);
	}
	RG.dfs(base-1,0);
	for(int i=0;i<n;i++){
		XX[LG.in[i]].push_back(RG.in[i]);
	}
	for(int i=0;i<q;i++){
		XQ[LG.out[Lidx[i]]].push_back(i);
	}
	seg seg_(n*2+100);
	for(int i=0;i<n_;i++){
		for(auto nxt:XX[i])seg_.update(nxt,i);
		for(auto nxt:XQ[i]){
			if(LG.in[Lidx[nxt]]<=seg_.f(RG.in[Ridx[nxt]],RG.out[Ridx[nxt]]))ret[nxt]=1;
			else ret[nxt]=0;
		}
	}
	return ret;
}

Compilation message (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:101:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |  for(int i=0;i<X.size();i++){
      |              ~^~~~~~~~~

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