Submission #340307

#	Time	Username	Problem	Language	Result	Execution time	Memory
340307		nikatamliani	Werewolf (IOI18_werewolf)	C++14	100 / 100	1977 ms	179692 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
const int NAX = 4e5+10, LG = 20;
vector<int> edges[NAX], tree[2][NAX], arr[2], ids; 
int in[2][NAX], out[2][NAX], p[2][NAX], L[2][NAX][LG];
int timer;
void add_edge(int x, int y, int which) {
	tree[which][x].push_back(y);
	tree[which][y].push_back(x); 
}
int find_set(int x, int which) {
	return x == p[which][x] ? x : p[which][x] = find_set(p[which][x], which);
}
void union_sets(int x, int y, int which) {
	x = find_set(x, which);
	y = find_set(y, which);
	if(x == y) {
		return;
	}
	p[which][y] = x; 
	add_edge(x, y, which);
}
void dfs(int x, int p, int which) {
	in[which][x] = ++timer;
	L[which][x][0] = p; 
	arr[which].push_back(x);
	for(int i = 1; i < LG; ++i) {
		int up = L[which][x][i - 1];
		L[which][x][i] = ~up ? L[which][up][i - 1] : -1; 
	}
	for(int to : tree[which][x]) {
		if(to != p) {
			dfs(to, x, which); 
		}
	}
	out[which][x] = timer;
}
int up(int x, int cutoff, int p) {
	for(int i = LG - 1; i >= 0; --i) {
		if(p == 0 && ~L[p][x][i] && L[p][x][i] >= cutoff) {
			x = L[p][x][i];
		}
		if(p == 1 && ~L[p][x][i] && L[p][x][i] <= cutoff) {
			x = L[p][x][i];
		}
	}
	return x;
}
struct node {
	vi v;
	void merge(vi a, vi b) {
		v.reserve((int)a.size() + (int)b.size());
		for(int i = 0, j = 0; i < (int)a.size() || j < (int)b.size();) {
			if(i < (int)a.size() && (j == (int)b.size() || a[i] < b[j])) {
				v.push_back(a[i]);
				++i;
			} else {
				v.push_back(b[j]);
				++j;
			}
		}
	}
	int less(int x) {
		int l = 0, r = (int)v.size() - 1, ans = -1;
		while(r >= l) {
			int m = l + r >> 1;
			if(v[m] <= x) {
				ans = m;
				l = m + 1;
			} else {
				r = m - 1;
			}
		}
		return ans+1;
	}
} t[4*NAX];
void build(int l, int r, int p) {
	if(l == r) {
		t[p].v = {arr[1][l - 1]}; 
	} else {
		int m = l + r >> 1;
		build(l, m, p << 1);
		build(m+1, r, p << 1 | 1);  
		t[p].merge(t[p << 1].v, t[p << 1 | 1].v);
	}
}
int query(int l, int r, int L, int R, int val, int p) {
	if(l > R || L > r) {
		return 0;
	}
	if(L <= l && R >= r) {
		return t[p].less(val);
	}
	int m = l + r >> 1;
	return query(l, m, L, R, val, p << 1) + query(m+1, r, L, R, val, p << 1 | 1); 
}
vector<int> check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) {
	for(int i = 0; i < X.size(); ++i) {
		edges[X[i]].push_back(Y[i]);
		edges[Y[i]].push_back(X[i]);
	}
	for(int i = 0; i < N; ++i) {
		p[0][i] = p[1][i] = i; 
	}
	for(int i = N - 1; i >= 0; --i) {
		for(int to : edges[i]) {
			if(to > i) {
				union_sets(i, to, 0); 
			}
		}
	}
	for(int i = 0; i < N; ++i) {
		for(int to : edges[i]) {
			if(to < i) {
				union_sets(i, to, 1);
			}
		}
	}
	timer = -1; dfs(0, -1, 0);
	timer = -1; dfs(N - 1, -1, 1);
	ids = vector<int>(N);
	for(int i = 0; i < N; ++i) {
		ids[arr[0][i]] = i; 
	} 
	for(int i = 0; i < N; ++i) {
		arr[1][i] = ids[arr[1][i]];  
	}
	build(1, N, 1);
	int Q = S.size();
	vi A(Q);
	for(int i = 0; i < Q; ++i) {
		int s = up(S[i], L[i], 0);
		int e = up(E[i], R[i], 1);
		int cnt = query(1, N, in[1][e]+1, out[1][e]+1, out[0][s], 1) - query(1, N, in[1][e]+1, out[1][e]+1, in[0][s]-1, 1); 
		A[i] = cnt > 0; 
	}
	return A;
}

Compilation message (stderr)

werewolf.cpp: In member function 'int node::less(int)':
werewolf.cpp:68:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |    int m = l + r >> 1;
      |            ~~^~~
werewolf.cpp: In function 'void build(int, int, int)':
werewolf.cpp:83:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   83 |   int m = l + r >> 1;
      |           ~~^~~
werewolf.cpp: In function 'int query(int, int, int, int, int, int)':
werewolf.cpp:96:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   96 |  int m = l + r >> 1;
      |          ~~^~~
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:100:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |  for(int i = 0; i < X.size(); ++i) {
      |                 ~~^~~~~~~~~~

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