Submission #554469

#	Time	Username	Problem	Language	Result	Execution time	Memory
554469		keta_tsimakuridze	Werewolf (IOI18_werewolf)	C++14	100 / 100	3551 ms	393700 KiB

werewolf

#include<bits/stdc++.h>
#include "werewolf.h"
using namespace std;
#define pii pair<int,int>
#define f first
#define s second
const int N = 4e5 + 5, inf = 1e9;
vector<int> V[2][N];
int cur[2], x[2][N], p[2][N][20], timer[2], tmin[2][N], tmout[2][N], pos[2][N], n;
int par[2][N];
vector<pii> edges;
set<int> s[4 * N];
int find(int u,int t) {
	return (par[t][u] == u ? u : par[t][u] = find(par[t][u], t));
}
void build(vector<pair<int,int> > edges, int t) {
	cur[t] = n; 
	for(int i = 1; i <= cur[t]; i++) par[t][i] = i;
	for(int i = 0; i < edges.size(); i++) {
		int u = edges[i].f, v = edges[i].s;
		if(find(u, t) != find(v, t)) {
			++cur[t]; par[t][cur[t]] = cur[t];
			V[t][cur[t]].push_back(find(u, t));
			V[t][cur[t]].push_back(find(v, t));
			x[t][cur[t]] = u;
			u = find(u, t), v = find(v, t);
			par[t][u] = cur[t];
			par[t][v] = cur[t];
			p[t][u][0] = p[t][v][0] = cur[t];
			
		}
	}
	cur[t]++; if(!t)x[t][cur[t]] = inf;
	for(int i = 1; i < cur[t]; i++) {
		if(find(i, t) == i) p[t][i][0] = cur[t], V[t][cur[t]].push_back(i);
	}
	for(int j = 1; j <= 18; j++) {
		for(int i = 1; i <= cur[t]; i++) {
			p[t][i][j] = p[t][p[t][i][j - 1]][j - 1];
		}
	}
}
void dfs(int u, int t) {
	if(u <= n) {
	tmin[t][u] = ++timer[t];
	pos[t][timer[t]] = u;
	}
	for(int i = 0; i < V[t][u].size(); i++) {
		dfs(V[t][u][i], t);
	}
	if(V[t][u].size()) tmin[t][u] = tmin[t][V[t][u][0]];
	tmout[t][u] = timer[t];
}
int get(int u,int t, int X) {
	for(int i = 18; i >= 0; i--) {
		if(!p[t][u][i]) continue;
		if(t && x[t][p[t][u][i]] >= X) u = p[t][u][i];
		else if(!t && x[t][p[t][u][i]] <= X) u = p[t][u][i];
	}
	return u;
}
void build(int u,int l,int r) {
	for(int i = l; i <= r; i++) if(pos[1][i] <= n)s[u].insert(tmin[0][pos[1][i]]);
	if(l == r) return;
	int mid = (l + r) / 2;
	build(2 * u, l, mid); build(2 * u + 1, mid + 1, r);
}
bool get(int u, int st,int en,int l,int r,int x,int y) {
	if(l > en || r < st) return 0;
	if(st <= l && r <= en) {
		if(s[u].upper_bound(x - 1) != s[u].end()) {
			if(*s[u].upper_bound(x - 1) <= y) return 1;
		}
		return 0;
	}
	int mid = (l + r) / 2;
	return get(2 * u, st, en, l, mid, x, y)|get(2 * u + 1, st, en, mid + 1, r, x, y);
}
 
std::vector<int> check_validity(int nn, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
    vector<pair<int,int> > edges; n = nn;
    for(int i = 0; i < X.size(); i++) {
    	++X[i]; ++Y[i];
    	edges.push_back({max(X[i], Y[i]), min(X[i], Y[i])});
	}
	
	sort(edges.begin(), edges.end()); 
	build(edges, 0); // werewolf
	
	for(int i = 0; i < edges.size(); i++) {
		swap(edges[i].f, edges[i].s);
	}
	sort(edges.rbegin(), edges.rend());
	build(edges, 1); // human
	dfs(cur[0], 0);
 
	
	dfs(cur[1], 1);
	
	build(1, 1, timer[1]);
	vector<int> ans(S.size());
 
	for(int i = 0; i < S.size(); i++) {
		int l = L[i], r = R[i], u = S[i], v = E[i];
		++l, ++r, ++u, ++v;
		if(u < l || v > r) {
			ans[i] = 0;
		
			continue;
		}
	
		u = get(u, 1, l);
		v = get(v, 0, r); 
		ans[i] = get(1, tmin[1][u], tmout[1][u], 1, timer[1], tmin[0][v], tmout[0][v]);
		
	}
	return ans;
 
}

Compilation message (stderr)

werewolf.cpp: In function 'void build(std::vector<std::pair<int, int> >, int)':
werewolf.cpp:19:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |  for(int i = 0; i < edges.size(); i++) {
      |                 ~~^~~~~~~~~~~~~~
werewolf.cpp: In function 'void dfs(int, int)':
werewolf.cpp:48:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |  for(int i = 0; i < V[t][u].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~
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:84:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     for(int i = 0; i < X.size(); i++) {
      |                    ~~^~~~~~~~~~
werewolf.cpp:92:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |  for(int i = 0; i < edges.size(); i++) {
      |                 ~~^~~~~~~~~~~~~~
werewolf.cpp:105:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |  for(int i = 0; i < S.size(); i++) {
      |                 ~~^~~~~~~~~~

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