| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 773427 |
2023-07-05T04:59:53 Z |
IBory |
Werewolf (IOI18_werewolf) |
C++17 |
|
4000 ms |
92784 KB |
#include "werewolf.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;
const int MAX = 200007;
int _P[MAX], P[18][MAX], D[MAX];
pii UD[18][MAX];
vector<int> TG[MAX], G[MAX];
int Find(int n) {
if (n == _P[n]) return n;
return _P[n] = Find(_P[n]);
}
int Union(int a, int b) {
a = Find(a), b = Find(b);
if (a == b) return 0;
_P[a] = b;
return 1;
}
void DFS(int cur, int prev) {
D[cur] = D[prev] + 1;
P[0][cur] = prev;
UD[0][cur] = {cur, cur};
for (int next : G[cur]) {
if (next == prev) continue;
DFS(next, cur);
}
}
int LCA(int a, int b) {
if (D[a] > D[b]) swap(a, b);
for (int i = 17; i >= 0; --i) if ((D[b] - D[a]) & (1 << i)) b = P[i][b];
if (a == b) return a;
for (int i = 17; i >= 0; --i) {
if (P[i][a] == P[i][b]) continue;
a = P[i][a], b = P[i][b];
}
return P[0][a];
}
pii PathQuery(int a, int b) {
int c = LCA(a, b);
//cout << a << ' ' << b << ' ' << c << '\n';
pii ret = {1e9, 0};
for (int i = 17; i >= 0; --i) {
if ((1 << i) & (D[a] + 1 - D[c])) {
ret.first = min(ret.first, UD[i][a].first);
ret.second = max(ret.second, UD[i][a].second);
//cout << "Up " << i << ' ' << a << '\n';
a = P[i][a];
}
if ((1 << i) & (D[b] + 1 - D[c])) {
ret.first = min(ret.first, UD[i][b].first);
ret.second = max(ret.second, UD[i][b].second);
//cout << "Up " << i << ' ' << b << '\n';
b = P[i][b];
}
}
return ret;
}
int KP(int a, int k) {
for (int i = 17; i >= 0; --i) if (k & (1 << i)) a = P[i][a];
return a;
}
int ToC(int a, int b, int c, int d) {
int cut = D[a] - D[c] + 1, dist = D[a] + D[b] - 2 * D[c] + 1;
if (d <= cut) return KP(a, d - 1);
return KP(b, dist - d);
}
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(), M = X.size();
for (int i = 0; i < M; ++i) {
TG[X[i]].push_back(Y[i]);
TG[Y[i]].push_back(X[i]);
}
for (int i = 0; i < N; ++i) sort(TG[i].begin(), TG[i].end(), greater<int>());
iota(_P, _P + N, 0);
for (int i = 0; i < N; ++i) {
for (int j : TG[i]) {
if (i < j || !Union(i, j)) continue;
//cout << "EDGE " << i << ' ' << j << '\n';
G[i].push_back(j);
G[j].push_back(i);
}
}
DFS(0, 0);
for (int i = 1; i < 18; ++i) for (int n = 0; n < N; ++n) {
P[i][n] = P[i - 1][P[i - 1][n]];
UD[i][n] = {min(UD[i - 1][n].first, UD[i - 1][P[i - 1][n]].first), max(UD[i - 1][n].second, UD[i - 1][P[i - 1][n]].second)};
//cout << i << ' ' << n << ' ' << UD[i][n].first << ' ' << UD[i][n].second << '\n';
}
vector<int> ans;
for (int i = 0; i < Q; ++i) {
int a = S[i], b = E[i], c = LCA(a, b);
int noA = L[i] - 1, noB = R[i] + 1;
pii pathInfo = PathQuery(a, b);
if (noA < pathInfo.first || pathInfo.second < noB) {
//cout << a << ' ' << b << " / " << pathInfo.first << ' ' << pathInfo.second << " SKIP\n";
ans.push_back(1);
continue;
}
int dist = D[a] + D[b] - 2 * D[c] + 1;
int qL = -1, qR = dist;
int bL = 0, bR = dist + 1;
while (bL + 1 < bR) {
int mid = (bL + bR) / 2;
pii t = PathQuery(a, ToC(a, b, c, mid));
(t.first <= noA ? bR : bL) = mid;
}
qR = bR;
bL = 0, bR = dist + 1;
while (bL + 1 < bR) {
int mid = (bL + bR) / 2;
pii t = PathQuery(b, ToC(b, a, c, mid));
(t.second >= noB ? bR : bL) = mid;
}
qL = dist + 1 - bR;
//cout << qL << ' ' << qR << '\n';
ans.push_back(qL + 1 < qR);
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
9940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
9940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4049 ms |
92784 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
9940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
