| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 678339 |
2023-01-05T13:32:11 Z |
1bin |
Werewolf (IOI18_werewolf) |
C++14 |
|
521 ms |
107224 KB |
#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
typedef long long ll;
const int B = 1 << 18;
ll n, m, q, par[B], a, b, d[B][2], u[B][2], t;
vector<int> adj[B], seg[B * 2];
vector<int> g[B], vl[B], vr[B];
int find(int x){return par[x] == -1 ? x : par[x] = find(par[x]);}
void dfs(int x, int f){
!f ? d[x][0] = t++ : u[x][0] = t++;
for(int& nx : g[x]) dfs(nx, f);
!f ? d[x][1] = t - 1 : u[x][1] = t - 1;
return;
}
int qry(int l, int r, int k){
l += B; r += B;
int ret = n;
while(l <= r){
if(l & 1){
auto it = lower_bound(all(seg[l]), k);
if(it != seg[l].end()) ret = min(ret, *it);
l++;
}
if(!(r & 1)){
auto it = lower_bound(all(seg[r]), k);
if(it != seg[r].end()) ret = min(ret, *it);
r--;
}
l /= 2; r /= 2;
}
return ret;
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
n = N, m = X.size(), q = S.size();
vector<int> A(q);
for(int i = 0; i < m; i++){
a = X[i]; b = Y[i];
adj[a].emplace_back(b);
adj[b].emplace_back(a);
}
for(int i = 0; i < q; i++){
vl[L[i]].emplace_back(i);
vr[R[i]].emplace_back(i);
}
memset(par, -1, sizeof(par));
for(int x = n - 1; x >= 0; x--){
for(int y : adj[x]){
if(y < x) continue;
y = find(y);
if(x == y) continue;
par[y] = x;
g[x].emplace_back(y);
}
for(int& i : vl[x])
S[i] = find(S[i]);
}
dfs(0, 0);
memset(par, -1, sizeof(par));
for(int i = 0; i < n; i++) g[i].clear();
for(int x = 0; x < n; x++) {
for(int y : adj[x]){
if(y > x) continue;
y = find(y);
if(x == y) continue;
par[y] = x;
g[x].emplace_back(y);
}
for(int& i : vr[x])
E[i] = find(E[i]);
}
t = 0; dfs(n - 1, 1);
for(int i = 0; i < n; i++) seg[B + u[i][0]].emplace_back(i);
for(int i = B - 1; i; i--){
seg[i].resize(seg[i * 2].size() + seg[i * 2 + 1].size());
merge(all(seg[i * 2]), all(seg[i * 2 + 1]), seg[i].begin());
}
for(int i = 0; i < q; i++){
a = u[E[i]][0]; b = u[E[i]][1];
if(qry(a, b, S[i]) == S[i]) A[i] = 1;
else A[i] = 0;
//cout << A[i] << ' ';
}
return A;
}
/*
int main(void){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m >> q;
vector<int> X(m), Y(m), S(q), E(q), L(q), R(q);
for(int i = 0; i < m; i++) cin >> X[i] >> Y[i];
for(int i = 0; i < q; i++) cin >> S[i] >> E[i] >> L[i] >> R[i];
check_validity(n, X, Y, S, E, L, R);
return 0;
}*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
39252 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
39252 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
521 ms |
107224 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
39252 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
