oj.uz

Submission #554466

# Submission time Handle Problem Language Result Execution time Memory
554466 2022-04-28T12:45:10 Z keta_tsimakuridze Werewolf (IOI18_werewolf) C++14
15 / 100
 1570 ms 389792 KB 
#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, 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) {
	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);
	}
	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, cur[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, cur[1], tmin[0][v], tmout[0][v]);
		
	}
	return ans;
 
}

Compilation message

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:46:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |  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:81:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for(int i = 0; i < X.size(); i++) {
      |                    ~~^~~~~~~~~~
werewolf.cpp:89: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]
   89 |  for(int i = 0; i < edges.size(); i++) {
      |                 ~~^~~~~~~~~~~~~~
werewolf.cpp:102:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |  for(int i = 0; i < S.size(); i++) {
      |                 ~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 94420 KB Output is correct
2 Correct 52 ms 94348 KB Output is correct
3 Correct 49 ms 94232 KB Output is correct
4 Correct 51 ms 94220 KB Output is correct
5 Correct 47 ms 94404 KB Output is correct
6 Correct 52 ms 94280 KB Output is correct
7 Correct 50 ms 94352 KB Output is correct
8 Correct 53 ms 94348 KB Output is correct
9 Correct 50 ms 94320 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 94420 KB Output is correct
2 Correct 52 ms 94348 KB Output is correct
3 Correct 49 ms 94232 KB Output is correct
4 Correct 51 ms 94220 KB Output is correct
5 Correct 47 ms 94404 KB Output is correct
6 Correct 52 ms 94280 KB Output is correct
7 Correct 50 ms 94352 KB Output is correct
8 Correct 53 ms 94348 KB Output is correct
9 Correct 50 ms 94320 KB Output is correct
10 Correct 68 ms 97912 KB Output is correct
11 Correct 64 ms 97824 KB Output is correct
12 Correct 63 ms 97860 KB Output is correct
13 Correct 82 ms 98112 KB Output is correct
14 Correct 59 ms 98068 KB Output is correct
15 Correct 60 ms 97996 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1570 ms 380252 KB Output is correct
2 Runtime error 552 ms 389792 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 94420 KB Output is correct
2 Correct 52 ms 94348 KB Output is correct
3 Correct 49 ms 94232 KB Output is correct
4 Correct 51 ms 94220 KB Output is correct
5 Correct 47 ms 94404 KB Output is correct
6 Correct 52 ms 94280 KB Output is correct
7 Correct 50 ms 94352 KB Output is correct
8 Correct 53 ms 94348 KB Output is correct
9 Correct 50 ms 94320 KB Output is correct
10 Correct 68 ms 97912 KB Output is correct
11 Correct 64 ms 97824 KB Output is correct
12 Correct 63 ms 97860 KB Output is correct
13 Correct 82 ms 98112 KB Output is correct
14 Correct 59 ms 98068 KB Output is correct
15 Correct 60 ms 97996 KB Output is correct
16 Correct 1570 ms 380252 KB Output is correct
17 Runtime error 552 ms 389792 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -