QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#208029 | #7338. Education Nightmare | Gamal74 | WA | 1186ms | 43152kb | C++20 | 2.9kb | 2023-10-09 03:49:05 | 2023-10-09 03:49:05 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
#define fi first
#define se second
#define pp push_back
#define all(x) (x).begin(), (x).end()
#define Ones(n) __builtin_popcount(n)
#define endl '\n'
#define mem(arrr, xx) memset(arrr,xx,sizeof arrr)
//#define int long long
#define debug(x) cout << (#x) << " = " << x << endl
void Gamal() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef Clion
freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
#endif
}
int dx[] = {+0, +0, -1, +1, +1, +1, -1, -1};
int dy[] = {-1, +1, +0, +0, +1, -1, +1, -1};
const double EPS = 1e-9;
const ll OO = 0X3F3F3F3F3F3F3F3F;
const int N = 2e5 + 5, INF = INT_MAX, MOD = 1e9 + 7, LOG = 20;
vector<int> adj[N];
int depth[N], up[N][LOG], n, timer, tin[N], tout[N], sub[N], mx, m;
void dfs(int u, int p) {
tin[u] = timer++;
sub[u] = 0;
for (auto v: adj[u]) {
if (v == p)continue;
depth[v] = depth[u] + 1;
up[v][0] = u;
dfs(v, u);
sub[u] += sub[v] + 1;
}
tout[u] = timer - 1;
}
bool isAncestor(int u, int v) {
return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int LCA(int u, int v) {
if (depth[u] < depth[v])
swap(u, v);
int k = depth[u] - depth[v];
for (int i = 0; i < LOG; ++i) {
if ((1 << i) & k) {
u = up[u][i];
}
}
if (u == v)
return u;
for (int i = LOG - 1; i >= 0; --i) {
if (up[u][i] != up[v][i]) {
u = up[u][i];
v = up[v][i];
}
}
return up[u][0];
}
int Kthancestor(int u, int k) {
if (k > depth[u])return 0;
for (int j = LOG - 1; j >= 0; --j) {
if (k & (1 << j)) {
u = up[u][j];
}
}
return u;
}
void build(int root) {
dfs(root, root);
up[root][0] = root;
for (int j = 1; j < LOG; ++j) {
for (int i = 0; i < n; ++i) {
up[i][j] = up[up[i][j - 1]][j - 1];
}
}
}
int dist(int u, int v) {
return depth[u] + depth[v] - 2 * depth[LCA(u, v)];
}
void solve() {
int s;
cin >> n >> s >> m;
s--, m--;
for (int i = 0; i < n; ++i)adj[i].clear();
for (int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v;
u--, v--;
adj[u].push_back(v);
adj[v].push_back(u);
}
timer = 0;
depth[s] = 0;
build(s);
int ans = 0;
for (int i = 0; i < n; ++i) {
if (isAncestor(i, m)) {
ans = max(ans, depth[i]);
continue;
}
ans = max(ans, dist(i, m) + depth[m]);
}
cout << ans << endl;
}
signed main() {
Gamal();
int t = 1;
cin >> t;
while (t--) {
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 11368kb
input:
1 4 2 3 1 2 1 3 1 4
output:
4
result:
ok 1 number(s): "4"
Test #2:
score: -100
Wrong Answer
time: 1186ms
memory: 43152kb
input:
14966 15 13 8 7 14 7 10 5 3 1 3 15 3 1 13 9 5 7 2 6 13 10 11 13 8 5 10 5 12 14 4 16 14 9 16 11 14 9 8 15 14 15 13 10 6 11 3 2 9 5 6 7 10 6 6 8 1 5 15 4 10 2 11 12 100 49 58 67 43 55 34 84 42 3 74 84 54 20 6 86 83 88 51 2 99 4 78 91 64 14 59 82 38 91 44 24 12 12 2 39 19 43 46 5 80 41 35 80 97 79 8 47...
output:
9 8 63 12 3 9 140 8 154 10 14 95 7 76 176 4 85 2 172 7 121 132 132 69 7 158 0 96 91 6 123 90 7 9 4 97 70 94 13 3 3 10 10 12 8 5 136 115 90 5 84 130 3 6 1 117 11 148 84 4 1 141 99 8 1 3 4 13 5 88 104 146 82 5 9 127 85 12 86 11 5 4 8 5 9 4 9 64 8 105 68 2 124 83 1 117 2 1 9 78 6 121 9 0 9 13 87 0 4 9 ...
result:
wrong answer 7th numbers differ - expected: '131', found: '140'