//Cgrader.cpp
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define all(x) begin(x), end(x)
#define sz(x) ((int) (x).size())
using ll = long long;
using ld = long double;
const int N = 2e5 + 10;
struct Query {
int s, e, l, r, i;
};
int color[N];
vector<int> g[N];
struct DSU {
int parent[N];
vector<int> comp[N];
DSU() {
iota(all(parent), 0);
for (int i = 0; i < N; ++i) {
comp[i].push_back(i);
}
}
int get(int u) {
if (u == parent[u]) {
return u;
}
return parent[u] = get(parent[u]);
}
} dsu;
struct DSU2 {
int parent[N], rank[N];
DSU2() {
iota(all(parent), 0);
}
int get(int u) {
if (u == parent[u]) {
return u;
}
return parent[u] = get(parent[u]);
}
bool merge(int a, int b) {
a = get(a);
b = get(b);
if (a == b) {
return false;
}
if (rank[a] == rank[b]) {
++rank[a];
}
if (rank[a] < rank[b]) {
swap(a, b);
}
parent[b] = a;
return true;
}
} dsu2;
bool check_reachable(int u, int barrier, int c, int p = -1) {
if (u < barrier) {
return false;
}
if (color[u] == c) {
return true;
}
for (int v : g[u]) {
if (v != p && check_reachable(v, barrier, c, u)) {
return true;
}
}
return false;
}
char used[N];
int sz[N];
int dfs_sz(int u, int p = -1) {
sz[u] = 1;
for (int v : g[u]) {
if (v != p && !used[v]) {
sz[u] += dfs_sz(v, u);
}
}
return sz[u];
}
int find_centroid(int u, int csz, int p = -1) {
for (int v : g[u]) {
if (v != p && !used[v] && sz[v] > 2 * csz) {
return find_centroid(v, csz, u);
}
}
return u;
}
struct Node {
weak_ptr<Node> parent;
vector<shared_ptr<Node>> children;
int version;
map<int, int> where;
map<int, int> mn;
Node(weak_ptr<Node> parent_) : parent(parent_) {}
};
int current_version = 15;
shared_ptr<Node> node_at[N];
shared_ptr<Node> centroid_dfs(int u, weak_ptr<Node> parent = {}) {
u = find_centroid(u, dfs_sz(u));
auto node = make_shared<Node>(parent);
node_at[u] = node;
node->parent = parent;
queue<tuple<int, int, int>> bfs;
bfs.push({u, u, -1});
while (sz(bfs)) {
auto [v, mn, p] = bfs.front();
node->where[v] = node->mn[v] = mn;
bfs.pop();
for (int w : g[v]) {
if (p != w && !used[w]) {
bfs.push({w, min(mn, w), v});
}
}
}
used[u] = 1;
for (int v : g[u]) {
if (!used[v]) {
node->children.push_back(centroid_dfs(v, node));
}
}
return node;
}
vector<int> check_validity(int, vector<int> us, vector<int> vs, vector<int> qs, vector<int> qe, vector<int> ql, vector<int> qr) {
vector<Query> queries;
for (int i = 0; i < sz(qs); ++i) {
queries.push_back({qe[i], qs[i], qr[i], ql[i], i});
}
vector<pair<int, int>> e1, e2;
for (int i = 0; i < sz(us); ++i) {
e1.emplace_back(us[i], vs[i]);
}
e2 = e1;
iota(all(color), 0);
sort(all(e1), [](const auto &x, const auto &y) {
return max(x.x, x.y) < max(y.x, y.y);
});
sort(all(e2), [](const auto &x, const auto &y) {
return min(x.x, x.y) > min(y.x, y.y);
});
for (auto [u, v] : e2) {
if (dsu2.merge(u, v)) {
g[u].push_back(v);
g[v].push_back(u);
}
}
sort(all(queries), [](const auto &x, const auto &y) {
return x.l < y.l;
});
vector<int> ans(sz(queries));
centroid_dfs(0);
int e1i = 0;
for (auto [s, e, l, r, i] : queries) {
while (e1i < sz(e1) && max(e1[e1i].x, e1[e1i].y) <= l) {
int a = dsu.get(e1[e1i].x), b = dsu.get(e1[e1i].y);
++e1i;
if (a == b) {
continue;
}
if (sz(dsu.comp[a]) < sz(dsu.comp[b])) {
swap(a, b);
}
++current_version;
for (int u : dsu.comp[b]) {
auto curr = node_at[u];
while (curr && curr->version != current_version) {
curr->version = current_version;
auto it = curr->where.find(a);
if (it == curr->where.end()) {
curr->where[a] = curr->where[b];
} else {
it->second = max(it->second, curr->where[b]);
}
curr = curr->parent.lock();
}
color[u] = a;
}
dsu.comp[a].insert(end(dsu.comp[a]), all(dsu.comp[b]));
vector<int>().swap(dsu.comp[b]);
dsu.parent[b] = a;
}
auto curr = node_at[e];
while (curr) {
if (curr->mn[e] >= r) {
auto it = curr->where.find(color[s]);
if (it != curr->where.end() && it->second >= r) {
ans[i] = 1;
break;
}
}
curr = curr->parent.lock();
}
// ans[i] = check_reachable(e, r, color[s]);
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
18388 KB |
Output is correct |
2 |
Correct |
16 ms |
18388 KB |
Output is correct |
3 |
Correct |
16 ms |
18416 KB |
Output is correct |
4 |
Correct |
16 ms |
18352 KB |
Output is correct |
5 |
Correct |
17 ms |
18460 KB |
Output is correct |
6 |
Correct |
17 ms |
18448 KB |
Output is correct |
7 |
Correct |
21 ms |
18552 KB |
Output is correct |
8 |
Correct |
17 ms |
18644 KB |
Output is correct |
9 |
Correct |
18 ms |
18448 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
18388 KB |
Output is correct |
2 |
Correct |
16 ms |
18388 KB |
Output is correct |
3 |
Correct |
16 ms |
18416 KB |
Output is correct |
4 |
Correct |
16 ms |
18352 KB |
Output is correct |
5 |
Correct |
17 ms |
18460 KB |
Output is correct |
6 |
Correct |
17 ms |
18448 KB |
Output is correct |
7 |
Correct |
21 ms |
18552 KB |
Output is correct |
8 |
Correct |
17 ms |
18644 KB |
Output is correct |
9 |
Correct |
18 ms |
18448 KB |
Output is correct |
10 |
Correct |
76 ms |
27200 KB |
Output is correct |
11 |
Correct |
55 ms |
23848 KB |
Output is correct |
12 |
Execution timed out |
4077 ms |
315020 KB |
Time limit exceeded |
13 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
4078 ms |
413376 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
18388 KB |
Output is correct |
2 |
Correct |
16 ms |
18388 KB |
Output is correct |
3 |
Correct |
16 ms |
18416 KB |
Output is correct |
4 |
Correct |
16 ms |
18352 KB |
Output is correct |
5 |
Correct |
17 ms |
18460 KB |
Output is correct |
6 |
Correct |
17 ms |
18448 KB |
Output is correct |
7 |
Correct |
21 ms |
18552 KB |
Output is correct |
8 |
Correct |
17 ms |
18644 KB |
Output is correct |
9 |
Correct |
18 ms |
18448 KB |
Output is correct |
10 |
Correct |
76 ms |
27200 KB |
Output is correct |
11 |
Correct |
55 ms |
23848 KB |
Output is correct |
12 |
Execution timed out |
4077 ms |
315020 KB |
Time limit exceeded |
13 |
Halted |
0 ms |
0 KB |
- |