oj.uz

Submission #92820

# Submission time Handle Problem Language Result Execution time Memory
92820 2019-01-05T08:23:28 Z psmao Werewolf (IOI18_werewolf) C++14
100 / 100
 1479 ms 145528 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;

#define fo(i,s,t) for(int i = s; i <= t; ++ i)
#define fd(i,s,t) for(int i = s; i >= t; -- i)
#define bf(i,s) for(int i = head[s]; i; i = e[i].next)
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pb push_back
#define VI vector<int>
#define sf scanf
#define pf printf
#define fp freopen
#define SZ(x) ((int)(x).size())
#ifdef MPS
#define D(x...) printf(x)
#else
#define D(x...)
#endif
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
const int inf = 1<<30;
const ll INF = 1ll<<60;
const db Inf = 1e20;
const db eps = 1e-9;

const int maxn = 200050;

int fa[maxn];
struct KruskalT
{
	VI adj[maxn];
	int tot, anc[maxn][20], in[maxn], out[maxn];
	void link(int u, int v) 
	{
		adj[u].emplace_back(v);
		anc[v][0] = u;
	}
	void init(int N)
	{
		fo(j,1,19) 
			for(int i = 0; i < N; ++ i)
				if(anc[i][j-1] != -1)
					anc[i][j] = anc[anc[i][j-1]][j-1];
	}
	int getsub(int u, int x, int oper) // oper = 0 => >= L[i], 1-> <=R[i]
	{
		if(oper == 0)
		{
			fd(i,19,0) 
				if(anc[u][i] != -1 && anc[u][i] >= x) 
					u = anc[u][i];
			if(u >= x) return u;
			else return -1;
		}
		else
		{
			fd(i,19,0)
				if(anc[u][i] != -1 && anc[u][i] <= x) 
					u = anc[u][i];
			if(u <= x) return u;
			else return -1;
		}
	}
	void dfs(int u)
	{
		in[u] = ++ tot;
		for(auto p : adj[u]) dfs(p);
		out[u] = tot;
	}
}Tu, Tv, T;
int ls[maxn*20], rs[maxn*20], nd[maxn*20], tot;
int rt[maxn], bag[maxn];

int getfa(int x){return fa[x] == x ? x : fa[x] = getfa(fa[x]);}
void add(int &now, int pre, int p, int l, int r)
{
	now = ++ tot;
	nd[now] = nd[pre] + 1; ls[now] = ls[pre]; rs[now] = rs[pre];
	if(l == r) return;
	int mid = l + r >> 1;
	if(p <= mid) add(ls[now], ls[pre], p, l, mid);
	else add(rs[now], rs[pre], p, mid+1, r);
}
int ask(int now, int pre, int l, int r, int L, int R)
{
	if(!now) return 0;
	if(l <= L && R <= r) return nd[now] - nd[pre];
	int mid = L + R >> 1;
	if(r <= mid) return ask(ls[now], ls[pre], l, r, L, mid);
	else if(l > mid) return ask(rs[now], rs[pre], l, r, mid+1, R);
	else return ask(ls[now], ls[pre], l, mid, L, mid) +
				ask(rs[now], rs[pre], mid+1, r, mid+1, R);
}
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 Q = S.size(), M = X.size();
  std::vector<int> A(Q);
  // construct two trees
  for(int i = 0; i < N; ++ i) fa[i] = i;
  memset(Tu.anc,0xff,sizeof(Tu.anc));
  memset(Tv.anc,0xff,sizeof(Tv.anc));
  for(int i = 0; i < M; ++ i) T.link(X[i], Y[i]), T.link(Y[i], X[i]);
  for(int i = N-1; i >= 0; -- i)
  {
  	for(auto p : T.adj[i]) if(p > i)
  	{
  		int fx = getfa(p);
  		if(fx != i)	{fa[fx] = i; Tu.link(i, fx); D("%d %d\n",i,fx);}
  	}
  }
  D("~~~~~~~~~~\n");
  for(int i = 0; i < N; ++ i) fa[i] = i;
  for(int i = 0; i < N; ++ i)
  {
  	for(auto p : T.adj[i]) if(p < i)
  	{
  		int fx = getfa(p);
  		if(fx != i) {fa[fx] = i; Tv.link(i, fx); D("%d %d\n",i,fx);}
  	}
  }
  D("~~~~~~~~~\n");
  //build up binary lifting stuffs
  Tu.init(N); Tv.init(N);
  Tu.dfs(0); Tv.dfs(N-1);
  //insert points into persistent rangetree
  for(int i = 0; i < N; ++ i) 
  	bag[Tu.in[i]] = Tv.in[i];
  for(int i = 1; i <= Tu.tot; ++ i) 
  {
  	add(rt[i], rt[i-1], bag[i], 1, Tv.tot);
  	D("%d\n",ask(rt[i],rt[i-1],bag[i],bag[i],1,Tv.tot));
  }
  //now query
  for(int i = 0; i < Q; ++ i)
  {
  	int x = Tu.getsub(S[i], L[i], 0), y = Tv.getsub(E[i], R[i], 1);
  	if(x == -1 || y == -1) {A[i] = 0; continue;}
  	D("%d %d %d\n",i,x,y);
  	D("[%d,%d] [%d,%d]\n",Tu.in[x],Tu.out[x],Tv.in[y],Tv.out[y]);
  	A[i] = ask(rt[Tu.out[x]], rt[Tu.in[x]-1], Tv.in[y], Tv.out[y], 1, Tv.tot);
  	A[i] = (A[i] > 0);
  }
  return A;
}

Compilation message

werewolf.cpp: In function 'void add(int&, int, int, int, int)':
werewolf.cpp:85:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~
werewolf.cpp: In function 'int ask(int, int, int, int, int, int)':
werewolf.cpp:93:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = L + R >> 1;
            ~~^~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 45816 KB Output is correct
2 Correct 39 ms 45816 KB Output is correct
3 Correct 39 ms 45816 KB Output is correct
4 Correct 39 ms 45816 KB Output is correct
5 Correct 41 ms 45816 KB Output is correct
6 Correct 40 ms 45816 KB Output is correct
7 Correct 40 ms 45816 KB Output is correct
8 Correct 40 ms 45816 KB Output is correct
9 Correct 40 ms 45816 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 45816 KB Output is correct
2 Correct 39 ms 45816 KB Output is correct
3 Correct 39 ms 45816 KB Output is correct
4 Correct 39 ms 45816 KB Output is correct
5 Correct 41 ms 45816 KB Output is correct
6 Correct 40 ms 45816 KB Output is correct
7 Correct 40 ms 45816 KB Output is correct
8 Correct 40 ms 45816 KB Output is correct
9 Correct 40 ms 45816 KB Output is correct
10 Correct 46 ms 47096 KB Output is correct
11 Correct 46 ms 47100 KB Output is correct
12 Correct 45 ms 47060 KB Output is correct
13 Correct 45 ms 47208 KB Output is correct
14 Correct 46 ms 47096 KB Output is correct
15 Correct 48 ms 47224 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 867 ms 136944 KB Output is correct
2 Correct 1091 ms 140792 KB Output is correct
3 Correct 953 ms 139364 KB Output is correct
4 Correct 875 ms 138640 KB Output is correct
5 Correct 836 ms 138704 KB Output is correct
6 Correct 811 ms 138528 KB Output is correct
7 Correct 674 ms 138620 KB Output is correct
8 Correct 790 ms 140536 KB Output is correct
9 Correct 760 ms 139276 KB Output is correct
10 Correct 619 ms 138744 KB Output is correct
11 Correct 644 ms 138744 KB Output is correct
12 Correct 669 ms 138760 KB Output is correct
13 Correct 1157 ms 145372 KB Output is correct
14 Correct 1163 ms 145452 KB Output is correct
15 Correct 1081 ms 145400 KB Output is correct
16 Correct 1159 ms 145332 KB Output is correct
17 Correct 837 ms 138548 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 45816 KB Output is correct
2 Correct 39 ms 45816 KB Output is correct
3 Correct 39 ms 45816 KB Output is correct
4 Correct 39 ms 45816 KB Output is correct
5 Correct 41 ms 45816 KB Output is correct
6 Correct 40 ms 45816 KB Output is correct
7 Correct 40 ms 45816 KB Output is correct
8 Correct 40 ms 45816 KB Output is correct
9 Correct 40 ms 45816 KB Output is correct
10 Correct 46 ms 47096 KB Output is correct
11 Correct 46 ms 47100 KB Output is correct
12 Correct 45 ms 47060 KB Output is correct
13 Correct 45 ms 47208 KB Output is correct
14 Correct 46 ms 47096 KB Output is correct
15 Correct 48 ms 47224 KB Output is correct
16 Correct 867 ms 136944 KB Output is correct
17 Correct 1091 ms 140792 KB Output is correct
18 Correct 953 ms 139364 KB Output is correct
19 Correct 875 ms 138640 KB Output is correct
20 Correct 836 ms 138704 KB Output is correct
21 Correct 811 ms 138528 KB Output is correct
22 Correct 674 ms 138620 KB Output is correct
23 Correct 790 ms 140536 KB Output is correct
24 Correct 760 ms 139276 KB Output is correct
25 Correct 619 ms 138744 KB Output is correct
26 Correct 644 ms 138744 KB Output is correct
27 Correct 669 ms 138760 KB Output is correct
28 Correct 1157 ms 145372 KB Output is correct
29 Correct 1163 ms 145452 KB Output is correct
30 Correct 1081 ms 145400 KB Output is correct
31 Correct 1159 ms 145332 KB Output is correct
32 Correct 837 ms 138548 KB Output is correct
33 Correct 1198 ms 138668 KB Output is correct
34 Correct 349 ms 68728 KB Output is correct
35 Correct 1425 ms 140252 KB Output is correct
36 Correct 1046 ms 139120 KB Output is correct
37 Correct 1376 ms 139768 KB Output is correct
38 Correct 1240 ms 139284 KB Output is correct
39 Correct 945 ms 145400 KB Output is correct
40 Correct 1145 ms 145384 KB Output is correct
41 Correct 1068 ms 139388 KB Output is correct
42 Correct 743 ms 139160 KB Output is correct
43 Correct 1479 ms 143656 KB Output is correct
44 Correct 1321 ms 139716 KB Output is correct
45 Correct 966 ms 145424 KB Output is correct
46 Correct 961 ms 145272 KB Output is correct
47 Correct 962 ms 145528 KB Output is correct
48 Correct 890 ms 145400 KB Output is correct
49 Correct 1074 ms 145456 KB Output is correct
50 Correct 1101 ms 145492 KB Output is correct
51 Correct 956 ms 145188 KB Output is correct
52 Correct 1042 ms 145244 KB Output is correct