#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN = 2e5 + 10;
struct DSU {
vector<int> par;
void init(int n) {
par.resize(n);
for(int i = 0; i < n; i ++) par[i] = i;
}
int get_root(int u) {
return par[u] == u ? u : par[u] = get_root(par[u]);
}
};
struct TGraph {
int root = 0;
vector<vector<int>> adj;
int timer = -1;
vector<int> in, out;
int up[mxN][20];
DSU lnk;
void init(int n) {
adj.resize(n);
in.resize(n);
out.resize(n);
lnk.init(n);
}
void addEdge(int u, int v) {
u = lnk.get_root(u);
v = lnk.get_root(v);
if(u == v) return ;
adj[u].push_back(v);
lnk.par[v] = u;
root = u;
}
void dfs(int u) {
in[u] = ++ timer;
for(int v : adj[u]) {
up[v][0] = u;
dfs(v);
}
out[u] = timer;
}
void build(int n) {
up[root][0] = root;
dfs(root);
for(int k = 1; k <= 18; k ++) {
for(int u = 0; u <= n - 1; u ++) {
up[u][k] = up[up[u][k - 1]][k - 1];
}
}
}
int get(int type, int u, int lim) {
if(type == 0) for(int k = 18; k >= 0; k --) if(up[u][k] >= lim) u = up[u][k];
if(type == 1) for(int k = 18; k >= 0; k --) if(up[u][k] <= lim) u = up[u][k];
return u;
}
};
vector<int> fen;
void update(int i, int x, int N) {
i ++ ;
for(; i <= N; i += i & (- i)) fen[i] += x;
}
int get(int i) {
int res = 0;
i ++ ;
for(; i > 0; i -= i & (- i)) res += fen[i];
return res;
}
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 Q = S.size();
int M = X.size();
vector<int> A(Q);
vector<vector<int>> g(N);
vector<vector<pair<int, int>>> k(N);
vector<int> id(N);
TGraph tr[2];
fen.resize(N + 1, 0);
for (int i = 0; i < Q; ++i) {
A[i] = 0;
}
for(int i = 0; i < M; i ++) {
g[X[i]].push_back(Y[i]);
g[Y[i]].push_back(X[i]);
}
tr[0].init(N);
tr[1].init(N);
for(int i = N - 1; i >= 0; i --) for(int j : g[i]) if(i < j) tr[0].addEdge(i, j);
for(int i = 0; i <= N - 1; i ++) for(int j : g[i]) if(i > j) tr[1].addEdge(i, j);
tr[0].build(N);
tr[1].build(N);
for(int i = 0; i <= Q - 1; i ++) {
int u = tr[0].get(0, S[i], L[i]);
E[i] = tr[1].get(1, E[i], R[i]);
k[tr[0].out[u]].push_back({i, 1});
if(tr[0].in[u]) k[tr[0].in[u] - 1].push_back({i, -1});
}
for(int i = 0; i <= N - 1; i ++) id[tr[0].in[i]] = i;
for(int i = 0; i <= N - 1; i ++) {
int x = id[i];
update(tr[1].in[x], 1, N);
for(auto [j, base] : k[i]) A[j] += base * (get(tr[1].out[E[j]]) - get(tr[1].in[E[j]]) - 1);
}
for(int i = 0; i <= Q - 1; i ++) A[i] = A[i] > 0;
return A;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
14 ms |
31576 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
14 ms |
31576 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
486 ms |
92108 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
14 ms |
31576 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |