oj.uz

Submission #1035285

# Submission time Handle Problem Language Result Execution time Memory
1035285 2024-07-26T08:50:09 Z lovrot Werewolf (IOI18_werewolf) C++17
15 / 100
 477 ms 524288 KB 
#include "werewolf.h"
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;

const int LOG = 18;
const int N = 1 << LOG;

struct quest {
	int l, r, a, b;
	quest() {}
	quest(int l, int r, int a, int b) : l(l), r(r), a(a), b(b) {}
};

quest q[N];
vector<int> g[N], h[N];

int un[N], iv[N], ma[N];

int trazi(int u) { 
	if(un[u] == -1) { 
		return u;
	}
	return un[u] = trazi(un[u]);
}

void unija(int u, int v) { 
	u = trazi(u);
	if(u == v) { return; }
	un[u] = v;
	h[v].PB(u);
}

int up[N][LOG], val[N];

void dfs(int u, vector<int> &p) { 
	iv[u] = p.size();
	for(int v : h[u]) { 
		up[v][0] = u;
//		printf("%d %d\n", u, v);
		dfs(v, p);
	}
	if(h[u].empty()) { 
		p.PB(u);
	}
	ma[u] = p.size();
}

int climb(int u, int x, bool f) { 
	for(int i = LOG - 1; i >= 0; --i) { 
		if((val[up[u][i]] >= x) == f) { 
			u = up[u][i];
		}
	}
	return u;
}

int t[2 * N]; // memset -1

void update(int u, int x) { 
	u += N;
	t[u] = x;
	for(u >>= 1; u; u >>= 1) { 
		t[u] = max(t[2 * u], t[2 * u + 1]);
	}
}

int query(int l, int r, int u = 1, int lo = 0, int hi = N) { 
	if(r <= lo || hi <= l) { return -1; }
	if(l <= lo && hi <= r) { return t[u]; }
	int mi = (lo + hi) / 2;
	return max(query(l, r, 2 * u, lo, mi), query(l, r, 2 * u + 1, mi, hi));
}

vector<int> qi[N];

vi check_validity(int n, vi X, vi Y, vi S, vi E, vi L, vi R) {
	int m = S.size();
	vector<int> ans(m);	
	
	for(int i = 0; i < X.size(); ++i) { 
		g[X[i]].PB(Y[i]);
		g[Y[i]].PB(X[i]);
	}
	
	// n - 1, n - 2, ... 0
	memset(un, -1, sizeof(un));
	for(int i = n - 2, j = n; i >= 0; --i, ++j) { 
		unija(i, j);
		val[j] = i;
		up[j][0] = j;
		for(int v : g[i]) { 
			if(v > i) {
				unija(v, j);
			}
		}
	}

	vector<int> a;
	dfs(2 * n - 2, a);
	for(int i = 1; i < LOG; ++i) { for(int j = 0; j < 2 * n - 1; ++j) { up[j][i] = up[up[j][i - 1]][i - 1]; } }
	for(int i = 0; i < m; ++i) { 
		int res = climb(S[i], L[i], 1);
		q[i].l = iv[res];
		q[i].r = ma[res];
		qi[q[i].r - 1].PB(i);
//		printf("%d %d lr %d %d\n", i, res, q[i].l, q[i].r);
	}

	// 0, 1, ... n - 1
	memset(un, -1, sizeof(un));
	for(int i = 1, j = n; i < n; ++i, ++j) {
		h[j].clear();
		unija(i, j);
		val[j] = i;
		up[j][0] = j;
		for(int v : g[i]) { 
			if(v < i) {
				unija(v, j);
			}
		}
	}

	vector<int> b;
	dfs(2 * n - 2, b);
	for(int i = 1; i < LOG; ++i) { for(int j = 0; j < 2 * n - 1; ++j) { 
		up[j][i] = up[up[j][i - 1]][i - 1]; } }
	for(int i = 0; i < m; ++i) { 
		int res = climb(E[i], R[i] + 1, 0);
		q[i].a = iv[res];
		q[i].b = ma[res];
//		printf("%d %d ab %d %d\n", i, res, q[i].a, q[i].b);
	}

//	for(int i = 0; i < n; ++i) { printf("(%d, %d)%c", i, a[i], " \n"[i == n - 1]); }
//	for(int i = 0; i < n; ++i) { printf("(%d, %d)%c", i, b[i], " \n"[i == n - 1]); }

	for(int i = 0; i < n; ++i) { 
		val[b[i]] = i;
	}

	memset(t, -1, sizeof(t));
	for(int i = 0; i < n; ++i) { 
		update(val[a[i]], i);
		for(int j : qi[i]) { 
//			printf("%d %d : %d %d %d %d\n", i, j, q[j].a, q[j].b, q[j].l, query(q[j].a, q[j].b + 1));
			if(query(q[j].a, q[j].b) >= q[j].l) { 
				ans[j] = 1;
			}
		}
	}
	
	return ans;
}

Compilation message

werewolf.cpp: In function 'vi check_validity(int, vi, vi, vi, vi, vi, vi)':
werewolf.cpp:91:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |  for(int i = 0; i < X.size(); ++i) {
      |                 ~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 21852 KB Output is correct
2 Correct 8 ms 21852 KB Output is correct
3 Correct 8 ms 21852 KB Output is correct
4 Correct 8 ms 21848 KB Output is correct
5 Correct 8 ms 21984 KB Output is correct
6 Correct 8 ms 21848 KB Output is correct
7 Correct 8 ms 21860 KB Output is correct
8 Correct 8 ms 21852 KB Output is correct
9 Correct 9 ms 21896 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 21852 KB Output is correct
2 Correct 8 ms 21852 KB Output is correct
3 Correct 8 ms 21852 KB Output is correct
4 Correct 8 ms 21848 KB Output is correct
5 Correct 8 ms 21984 KB Output is correct
6 Correct 8 ms 21848 KB Output is correct
7 Correct 8 ms 21860 KB Output is correct
8 Correct 8 ms 21852 KB Output is correct
9 Correct 9 ms 21896 KB Output is correct
10 Correct 11 ms 23132 KB Output is correct
11 Correct 14 ms 23092 KB Output is correct
12 Correct 13 ms 22872 KB Output is correct
13 Correct 12 ms 23276 KB Output is correct
14 Correct 12 ms 23132 KB Output is correct
15 Correct 13 ms 23132 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Runtime error 477 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 21852 KB Output is correct
2 Correct 8 ms 21852 KB Output is correct
3 Correct 8 ms 21852 KB Output is correct
4 Correct 8 ms 21848 KB Output is correct
5 Correct 8 ms 21984 KB Output is correct
6 Correct 8 ms 21848 KB Output is correct
7 Correct 8 ms 21860 KB Output is correct
8 Correct 8 ms 21852 KB Output is correct
9 Correct 9 ms 21896 KB Output is correct
10 Correct 11 ms 23132 KB Output is correct
11 Correct 14 ms 23092 KB Output is correct
12 Correct 13 ms 22872 KB Output is correct
13 Correct 12 ms 23276 KB Output is correct
14 Correct 12 ms 23132 KB Output is correct
15 Correct 13 ms 23132 KB Output is correct
16 Runtime error 477 ms 524288 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -