# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
729636 | t6twotwo | Werewolf (IOI18_werewolf) | C++17 | 200 ms | 71636 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
int M = X.size();
int Q = S.size();
vector<vector<int>> adj(N);
for (int i = 0; i < M; i++) {
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
if (N <= 3000 && M <= 6000 && Q <= 3000) {
vector<int> p(N);
function<int(int)> find = [&](int x) {
return x == p[x] ? x : p[x] = find(p[x]);
};
vector<vector<int>> s(N);
auto unite = [&](int x, int y) {
x = find(x);
y = find(y);
if (x == y) {
return;
}
if (s[x].size() > s[y].size()) {
swap(x, y);
}
for (int z : s[x]) {
p[z] = y;
s[y].push_back(z);
}
};
for (int i = 0; i < N; i++) {
p[i] = i;
s[i] = {i};
}
vector hi(N, vector<int>(N, -1));
for (int x = N - 1; x >= 0; x--) {
hi[x][x] = x;
for (int y : adj[x]) {
if (y < x || find(x) == find(y)) {
continue;
}
for (int u : s[find(x)]) {
for (int v : s[find(y)]) {
hi[u][v] = x;
hi[v][u] = x;
}
}
unite(x, y);
}
}
for (int i = 0; i < N; i++) {
p[i] = i;
s[i] = {i};
}
vector lo(N, vector<int>(N, -1));
for (int x = 0; x < N; x++) {
lo[x][x] = x;
for (int y : adj[x]) {
if (y > x || find(x) == find(y)) {
continue;
}
for (int u : s[find(x)]) {
for (int v : s[find(y)]) {
lo[u][v] = x;
lo[v][u] = x;
}
}
unite(x, y);
}
}
vector<int> ans(Q);
for (int i = 0; i < Q; i++) {
for (int j = L[i]; j <= R[i]; j++) {
if (hi[S[i]][j] >= L[i] && lo[j][E[i]] <= R[i]) {
ans[i] = 1;
}
}
}
return ans;
} else {
vector<int> A;
for (int i = 0; i < N; i++) {
if (adj[i].size() == 1) {
A.push_back(i);
A.push_back(adj[i][0]);
break;
}
}
while (A.size() < N) {
int x = A[A.size() - 2];
int y = A[A.size() - 1];
A.push_back(adj[y][0] ^ adj[y][1] ^ x);
}
vector<int> B(N);
for (int i = 0; i < N; i++) {
B[A[i]] = i;
}
vector<int> ans(Q);
for (int i = 0; i < Q; i++) {
if (S[i] < L[i] || E[i] > R[i]) {
continue;
}
int x = B[S[i]], u = -1;
int y = B[E[i]], v = -1;
if (x < y) {
u = x; assert(A[u] >= L[i]);
while (u + 1 <= y && A[u + 1] >= L[i]) {
u++;
}
v = y; assert(A[v] <= R[i]);
while (v - 1 >= x && A[v - 1] <= R[i]) {
v--;
}
} else {
u = x; assert(A[u] <= R[i]);
while (u + 1 <= y && A[u + 1] <= R[i]) {
u++;
}
v = y; assert(A[v] >= L[i]);
while (v - 1 >= x && A[v - 1] >= L[i]) {
v--;
}
}
if (v <= u) {
ans[i] = 1;
}
}
return ans;
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |