QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#379963 | #8575. Three Person Tree Game | ucup-team027# | WA | 23ms | 3832kb | C++23 | 2.3kb | 2024-04-06 20:15:34 | 2024-04-06 20:15:49 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
template <typename T> using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<class T>
struct RMQ {
vector<vector<T>> jmp;
RMQ(const vector<T>& V) : jmp(1, V) {
for (int pw = 1, k = 1; pw * 2 <= sz(V); pw *= 2, ++k) {
jmp.emplace_back(sz(V) - pw * 2 + 1);
rep(j,0,sz(jmp[k]))
jmp[k][j] = min(jmp[k - 1][j], jmp[k - 1][j + pw]);
}
}
T query(int a, int b) {
assert(a < b); // or return inf if a == b
int dep = 31 - __builtin_clz(b - a);
return min(jmp[dep][a], jmp[dep][b - (1 << dep)]);
}
};
struct LCA {
int T = 0;
vi time, path, ret, depth;
RMQ<int> rmq;
LCA(vector<vi>& C) : time(sz(C)), depth(sz(C)), rmq((dfs(C,0,-1), ret)) {}
void dfs(vector<vi>& C, int v, int par) {
time[v] = T++; if (par != -1) depth[v] = depth[par]+1;
for (int y : C[v]) if (y != par) {
path.push_back(v), ret.push_back(time[v]);
dfs(C, y, v);
}
}
int lca(int a, int b) {
if (a == b) return a;
tie(a, b) = minmax(time[a], time[b]);
return path[rmq.query(a, b)];
}
int dist(int a, int b){return depth[a] + depth[b] - 2*depth[lca(a,b)];}
};
void solve() {
int n; cin >> n;
int a, b, c;
cin >> a >> b >> c; a--, b--, c--;
vector<vector<int>> g(n);
for (int i = 1; i < n; i++) {
int x, y; cin >> x >> y; x--, y--;
g[x].push_back(y);
g[y].push_back(x);
}
LCA lca(g);
int mndist = 998244353, piv = 0;
for (int i = 0; i < n; i++) {
int dist = 0;
dist += lca.dist(a, i);
dist += lca.dist(b, i);
dist += lca.dist(c, i);
if (dist < mndist) {
mndist = dist;
piv = i;
}
}
int da = lca.dist(a, piv);
int db = lca.dist(b, piv);
int dc = lca.dist(c, piv);
// a win?
if (da <= dc+1 && db > da) {
cout << "A\n"; return;
}
// b win?
if (db <= da && dc > db) {
cout << "B\n"; return;
}
// c win?
if (dc <= db && da > dc+1) {
cout << "C\n"; return;
}
// draw
cout << "DRAW\n";
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
int t; cin >> t;
while (t--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3832kb
input:
2 3 1 2 3 2 1 3 1 4 1 2 3 1 4 2 4 3 4
output:
A DRAW
result:
ok 2 lines
Test #2:
score: -100
Wrong Answer
time: 23ms
memory: 3584kb
input:
10000 20 2 12 1 16 15 3 2 16 17 14 13 11 12 9 8 10 9 18 17 6 5 18 19 13 12 5 4 7 6 20 19 14 15 3 4 11 10 1 2 8 7 20 12 13 1 18 13 12 11 19 15 17 16 10 14 4 2 15 11 6 5 3 2 4 13 20 8 11 9 3 7 14 16 5 8 5 4 9 6 10 3 1 2 17 2 17 15 9 10 5 4 9 8 2 11 6 7 8 7 13 4 2 3 6 15 5 6 17 8 2 1 3 4 16 7 14 5 3 12...
output:
A B C B DRAW C A A A DRAW C B B B DRAW A DRAW A C DRAW DRAW B A A A B B B C A A A B B DRAW C DRAW A A DRAW A A B B DRAW C DRAW A B DRAW B DRAW A C DRAW DRAW B C DRAW DRAW A A DRAW DRAW DRAW B B B A DRAW B B A A DRAW B A A B DRAW A B A C DRAW A B A A DRAW B B B A A B B A C DRAW B A B DRAW A A C A A D...
result:
wrong answer 21st lines differ - expected: 'A', found: 'DRAW'