Submission #169677

#	Time	Username	Problem	Language	Result	Execution time	Memory
169677		dennisstar	Werewolf (IOI18_werewolf)	C++11	100 / 100	861 ms	95472 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define ryan bear
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
typedef vector<int> vi;
 
vi ans;
int N;
vi X, Y, S, E, L, R;
vi V[200010];
int t1[400010], t2[400010];
int top;
int par[200010]; int dep[200010];
int im[200010];
pii ar[200010];
 
struct Query {
	int s, l; //e, r
	int n, nd;
};
 
struct tree {
	vi child[400010];
	int s[400010], e[400010];
	int tp=0;
	void dfs(int now) {
		s[now]=e[now]=tp; tp++;
		for (int i:child[now]) {
			dfs(i);
			s[now]=min(s[now], s[i]);
			e[now]=max(e[now], e[i]);
		}
	}
}tS, tE;
 
Query Qs[200010], Qe[200010];
 
bool cmp1(Query q1, Query q2) {return q1.l>q2.l;}
bool cmp2(Query q1, Query q2) {return q1.l<q2.l;}
bool cmp3(Query q1, Query q2) {return q1.n<q2.n;}
 
void Union(int a, int b, bool type) {
	while (par[a]) a=par[a];
	while (par[b]) b=par[b];
	if (a==b) return ;
	if (dep[a]<dep[b]) swap(a, b);
	par[b]=a; dep[a]=max(dep[a], dep[b]+1);
 
	if (!type) t1[im[a]]=top, t1[im[b]]=top, tS.child[top].push_back(im[a]), tS.child[top].push_back(im[b]);
	else t2[im[a]]=top, t2[im[b]]=top, tE.child[top].push_back(im[a]), tE.child[top].push_back(im[b]);
 
	im[a]=top++;
}
 
void f1() {
	top=N;
	memset(dep, 0, sizeof(dep));
	memset(par, 0, sizeof(par));
	for (int i=0; i<N; i++) im[i]=i;
	for (int i=N-1, k=0; i>=0; i--) {
		for (int j:V[i]) {
			if (j<i) continue;
			Union(i, j, false);
		}
		for (; k<S.size() && i==Qs[k].l; k++) {
			int l=Qs[k].s; while(par[l]) l=par[l];
			Qs[k].nd=im[l];
		}
	}
	for (int i=0; i<top; i++) tS.s[i]=tS.e[i]=i;
	tS.dfs(top-1);
}
 
void f2() {
	top=N;
	memset(dep, 0, sizeof(dep));
	memset(par, 0, sizeof(par));
	for (int i=0; i<N; i++) im[i]=i;
	for (int i=0, k=0; i<N; i++) {
		for (int j:V[i]) {
			if (j>i) continue;
			Union(i, j, true);
		}
		for (; k<S.size() && i==Qe[k].l; k++) {
			int l=Qe[k].s; while(par[l]) l=par[l];
			Qe[k].nd=im[l];
		}
	}
	for (int i=0; i<top; i++) tE.s[i]=tE.e[i]=i;
	tE.dfs(top-1);
}
 
struct fQ_ {
	int x1, x2, y1, y2;
	int Qn, ans;
}fQ[200010];
int seg[(1<<20)];
bool cmp4(fQ_ q1, fQ_ q2) {return q1.x2<q2.x2;}
bool cmp5(fQ_ q1, fQ_ q2) {return q1.Qn<q2.Qn;}
vi check_validity(int N_, vi X_, vi Y_, vi S_, vi E_, vi L_, vi R_) {
	N=N_; X=X_; Y=Y_; S=S_; E=E_; L=L_; R=R_;
	for (int i=0; i<X.size(); i++) {
		V[X[i]].push_back(Y[i]);
		V[Y[i]].push_back(X[i]);
	}
	for (int i=0; i<S.size(); i++) {
		Qs[i]={S[i],L[i],i};
		Qe[i]={E[i],R[i],i};
	}
	sort(Qs, Qs+S.size(), cmp1);
	sort(Qe, Qe+S.size(), cmp2);
	f1(); f2();
	sort(Qs, Qs+S.size(), cmp3);
	sort(Qe, Qe+S.size(), cmp3);
	int nd1, nd2;
	for (int i=0; i<S.size(); i++) {
		nd1=Qs[i].nd; nd2=Qe[i].nd;
		fQ[i]={tS.s[nd1], tS.e[nd1], tE.s[nd2], tE.e[nd2], i, 0};
	}
	sort(fQ, fQ+S.size(), cmp4);
	for (int i=0; i<N; i++) ar[i]={tS.s[i], tE.s[i]};
	sort(ar, ar+N);
	int t=0;
	int fr, re, mx;
	for (int i=0; i<S.size(); i++) {
		for (; t<N&&ar[t].fi<=fQ[i].x2; t++) {
			for (int j=(1<<19)+ar[t].se; j; j/=2) seg[j]=max(seg[j], ar[t].fi);
		}
		fr=fQ[i].y1+(1<<19), re=fQ[i].y2+(1<<19), mx=0;
		while (fr<=re) {
			if (fr%2) mx=max(mx, seg[fr++]);
			if (re%2==0) mx=max(mx, seg[re--]);
			fr/=2; re/=2;
		}
		if (mx>=fQ[i].x1) fQ[i].ans=1;
		else fQ[i].ans=0;
	}
	sort(fQ, fQ+S.size(), cmp5);
	for (int i=0; i<S.size(); i++) ans.push_back(fQ[i].ans);
	return ans;
}

Compilation message (stderr)

werewolf.cpp: In function 'void f1()':
werewolf.cpp:71:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (; k<S.size() && i==Qs[k].l; k++) {
          ~^~~~~~~~~
werewolf.cpp: In function 'void f2()':
werewolf.cpp:90:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (; k<S.size() && i==Qe[k].l; k++) {
          ~^~~~~~~~~
werewolf.cpp: In function 'vi check_validity(int, vi, vi, vi, vi, vi, vi)':
werewolf.cpp:108:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<X.size(); i++) {
                ~^~~~~~~~~
werewolf.cpp:112:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<S.size(); i++) {
                ~^~~~~~~~~
werewolf.cpp:122:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<S.size(); i++) {
                ~^~~~~~~~~
werewolf.cpp:131:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<S.size(); i++) {
                ~^~~~~~~~~
werewolf.cpp:145:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<S.size(); i++) ans.push_back(fQ[i].ans);
                ~^~~~~~~~~

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