oj.uz

Submission #169677

# Submission time Handle Problem Language Result Execution time Memory
169677 2019-12-22T05:46:00 Z dennisstar Werewolf (IOI18_werewolf) C++11
100 / 100
 861 ms 95472 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 25592 KB Output is correct
2 Correct 26 ms 25592 KB Output is correct
3 Correct 30 ms 25464 KB Output is correct
4 Correct 39 ms 25592 KB Output is correct
5 Correct 26 ms 25464 KB Output is correct
6 Correct 26 ms 25464 KB Output is correct
7 Correct 26 ms 25464 KB Output is correct
8 Correct 32 ms 25592 KB Output is correct
9 Correct 26 ms 25464 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 25592 KB Output is correct
2 Correct 26 ms 25592 KB Output is correct
3 Correct 30 ms 25464 KB Output is correct
4 Correct 39 ms 25592 KB Output is correct
5 Correct 26 ms 25464 KB Output is correct
6 Correct 26 ms 25464 KB Output is correct
7 Correct 26 ms 25464 KB Output is correct
8 Correct 32 ms 25592 KB Output is correct
9 Correct 26 ms 25464 KB Output is correct
10 Correct 33 ms 26616 KB Output is correct
11 Correct 34 ms 26616 KB Output is correct
12 Correct 34 ms 26616 KB Output is correct
13 Correct 33 ms 26616 KB Output is correct
14 Correct 33 ms 26616 KB Output is correct
15 Correct 34 ms 26616 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 822 ms 86932 KB Output is correct
2 Correct 685 ms 88804 KB Output is correct
3 Correct 682 ms 87524 KB Output is correct
4 Correct 786 ms 89816 KB Output is correct
5 Correct 737 ms 91628 KB Output is correct
6 Correct 771 ms 91460 KB Output is correct
7 Correct 756 ms 91500 KB Output is correct
8 Correct 687 ms 93632 KB Output is correct
9 Correct 646 ms 92216 KB Output is correct
10 Correct 678 ms 91664 KB Output is correct
11 Correct 725 ms 91456 KB Output is correct
12 Correct 737 ms 91500 KB Output is correct
13 Correct 687 ms 92780 KB Output is correct
14 Correct 685 ms 92800 KB Output is correct
15 Correct 747 ms 92840 KB Output is correct
16 Correct 712 ms 92808 KB Output is correct
17 Correct 760 ms 91352 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 25592 KB Output is correct
2 Correct 26 ms 25592 KB Output is correct
3 Correct 30 ms 25464 KB Output is correct
4 Correct 39 ms 25592 KB Output is correct
5 Correct 26 ms 25464 KB Output is correct
6 Correct 26 ms 25464 KB Output is correct
7 Correct 26 ms 25464 KB Output is correct
8 Correct 32 ms 25592 KB Output is correct
9 Correct 26 ms 25464 KB Output is correct
10 Correct 33 ms 26616 KB Output is correct
11 Correct 34 ms 26616 KB Output is correct
12 Correct 34 ms 26616 KB Output is correct
13 Correct 33 ms 26616 KB Output is correct
14 Correct 33 ms 26616 KB Output is correct
15 Correct 34 ms 26616 KB Output is correct
16 Correct 822 ms 86932 KB Output is correct
17 Correct 685 ms 88804 KB Output is correct
18 Correct 682 ms 87524 KB Output is correct
19 Correct 786 ms 89816 KB Output is correct
20 Correct 737 ms 91628 KB Output is correct
21 Correct 771 ms 91460 KB Output is correct
22 Correct 756 ms 91500 KB Output is correct
23 Correct 687 ms 93632 KB Output is correct
24 Correct 646 ms 92216 KB Output is correct
25 Correct 678 ms 91664 KB Output is correct
26 Correct 725 ms 91456 KB Output is correct
27 Correct 737 ms 91500 KB Output is correct
28 Correct 687 ms 92780 KB Output is correct
29 Correct 685 ms 92800 KB Output is correct
30 Correct 747 ms 92840 KB Output is correct
31 Correct 712 ms 92808 KB Output is correct
32 Correct 760 ms 91352 KB Output is correct
33 Correct 799 ms 92144 KB Output is correct
34 Correct 494 ms 67820 KB Output is correct
35 Correct 807 ms 93164 KB Output is correct
36 Correct 861 ms 90988 KB Output is correct
37 Correct 782 ms 92424 KB Output is correct
38 Correct 783 ms 90864 KB Output is correct
39 Correct 772 ms 94832 KB Output is correct
40 Correct 849 ms 95472 KB Output is correct
41 Correct 752 ms 91632 KB Output is correct
42 Correct 731 ms 90256 KB Output is correct
43 Correct 841 ms 94084 KB Output is correct
44 Correct 855 ms 91628 KB Output is correct
45 Correct 720 ms 94036 KB Output is correct
46 Correct 713 ms 93680 KB Output is correct
47 Correct 689 ms 90820 KB Output is correct
48 Correct 686 ms 90512 KB Output is correct
49 Correct 682 ms 90476 KB Output is correct
50 Correct 684 ms 90380 KB Output is correct
51 Correct 846 ms 95060 KB Output is correct
52 Correct 861 ms 95156 KB Output is correct