Submission #1090117

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090117		StefanSebez	Werewolf (IOI18_werewolf)	C++14	100 / 100	508 ms	120796 KiB

werewolf

#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=2e5+50,lg=19;
struct DSU{
	int par[N+50],in[N+50],out[N+50],nc,a[N+50],Par[N+50][lg+1],sajz[N+50];
	vector<int>E[N+50];
	void Init(){for(int i=0;i<=N;i++)par[i]=i,nc=0,sajz[i]=1;}
	int FS(int u){if(par[u]==u) return u;return par[u]=FS(par[u]);}
	void US(int u,int v){par[FS(u)]=FS(v);}//{if(sajz[u]>sajz[v]) swap(u,v);par[v]=u;sajz[v]+=sajz[u];}
	void AddEdge(int u,int v){if(u!=v){E[u].pb(v),E[v].pb(u);}}
	void DFS(int u,int parent){
		//printf("%i %i\n",u-1,parent-1);
		in[u]=++nc;a[nc]=u;Par[u][0]=parent;
		for(int i=1;i<=lg;i++) Par[u][i]=Par[Par[u][i-1]][i-1];
		for(auto i:E[u]) if(i!=parent) DFS(i,u);
		out[u]=nc;
	}
	int NadjiL(int u,int x){for(int i=lg;i>=0;i--) if(Par[u][i] && Par[u][i]<=x) u=Par[u][i];return u;}
	int NadjiR(int u,int x){for(int i=lg;i>=0;i--) if(Par[u][i]>=x) u=Par[u][i];return u;}
}dsu[2];
int ind[N+50];
vector<int>E[N+50];
vector<array<int,5> >Qs;
vector<array<int,5> >ev[N+50];
int T[N+50];
void Update(int i,int qval){for(;i<=N;i+=i&-i)T[i]+=qval;}
int Get(int i){int res=0;for(;i>=1;i-=i&-i)res+=T[i];return res;}
std::vector<int> check_validity(int n, std::vector<int> X, std::vector<int> Y,std::vector<int> U, std::vector<int> V,std::vector<int> L, std::vector<int> R) {
	int q=U.size();
	for(int i=0;i<q;i++) U[i]++,V[i]++,L[i]++,R[i]++;
	for(int i=0;i<X.size();i++){
		X[i]++,Y[i]++;
		int u=X[i],v=Y[i];
		E[u].pb(v);E[v].pb(u);
	}
	dsu[0].Init(),dsu[1].Init();
	for(int i=1;i<=n;i++){
		for(auto j:E[i]) if(j<i && dsu[0].FS(j)!=dsu[0].FS(i)) {dsu[0].AddEdge(dsu[0].FS(j),i);dsu[0].US(j,i);}
		//for(int j=1;j<=n;j++) printf("%i %i\n",dsu[0].par[j]-1,j-1);printf("\n");
	}
	dsu[0].DFS(n,0);
	//printf("\n");
	for(int i=n;i>=1;i--) for(auto j:E[i]) if(j>i && dsu[1].FS(j)!=dsu[1].FS(i)) {dsu[1].AddEdge(dsu[1].FS(j),i);dsu[1].US(j,i);}
	dsu[1].DFS(1,0);
	//for(int i=1;i<=n;i++) printf("%i ",dsu[0].a[i]-1);printf("\n");
	//for(int i=1;i<=n;i++) printf("%i %i\n",dsu[0].in[i],dsu[0].out[i]);printf("\n");
	for(int i=1;i<=n;i++) ind[dsu[1].a[i]]=i;
	vector<int>res(q,0);
	for(int I=0;I<q;I++){
		int u=U[I],v=V[I],l=L[I],r=R[I];
		int v1=dsu[0].NadjiL(v,r),u1=dsu[1].NadjiR(u,l);
		Qs.pb({dsu[0].in[v1],dsu[0].out[v1],dsu[1].in[u1],dsu[1].out[u1],I});
		ev[dsu[0].in[v1]-1].pb({dsu[1].in[u1],dsu[1].out[u1],I,-1});
		ev[dsu[0].out[v1]].pb({dsu[1].in[u1],dsu[1].out[u1],I,1});
	}
	for(int i=1;i<=n;i++){
		Update(ind[dsu[0].a[i]],1);
		for(auto j:ev[i]){
			int bul=j[3];
			res[j[2]]+=bul*(Get(j[1])-Get(j[0]-1));
		}
	}
	for(int i=0;i<q;i++) if(res[i]) res[i]=1;
	return res;
}

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

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