QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#379795 | #8575. Three Person Tree Game | ucup-team228# | AC ✓ | 62ms | 17380kb | C++20 | 4.5kb | 2024-04-06 19:09:30 | 2024-04-06 19:09:31 |
Judging History
answer
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx2") // doesn't work on Yandex
//#pragma GCC target("avx") // for old judges
//#pragma GCC target("bmi,bmi2,lzcnt,popcnt") // fast bit operations
#include <iostream>
#include <iomanip>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <queue>
#include <deque>
#include <cmath>
#include <algorithm>
#include <cassert>
#include <chrono>
#include <random>
#include <string>
#include <numeric>
#include <complex>
#include <tuple>
#include <utility>
#include <bitset>
#include <array>
#include <stack>
#include <sstream>
#include <unordered_set>
using namespace std;
typedef long long ll;
string to_string(string a) { return '"' + a + '"'; }
string to_string(char a) { return "'" + string(1, a) + "'"; }
string to_string(const char* a) { return to_string((string) a); }
string to_string(bool a) { return a ? "true" : "false"; }
template <class T1, class T2>
string to_string(pair<T1, T2> a) {
return "(" + to_string(a.first) + ", " + to_string(a.second) + ")";
}
template <class T>
string to_string(T a) {
bool first = true; string res = "{";
for (const auto& i : a) {
if (!first) res += ", ";
first = false;
res += to_string(i);
}
res += "}";
return res;
}
void debug_out() { cerr << endl; }
template <class T1, class... T2>
void debug_out(T1 a, T2... b) {
cerr << " " << to_string(a);
debug_out(b...);
}
#ifdef LOCAL
#define out(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define out(...) 42
#endif
clock_t start_time; void start_timer() { start_time = clock(); }
double get_time() { return (double) (clock() - start_time) / CLOCKS_PER_SEC; }
void Solve();
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef LOCAL
freopen("usr/share/man/man1/input.txt", "r", stdin);
#endif
start_timer();
Solve();
#ifdef LOCAL
cerr << fixed << setprecision(3);
cerr << endl << "Time spent: " << get_time() << endl;
#endif
return 0;
}
// do something, stay focused
// look for stupid bugs
// guess, slow, stress
// don't overgeneralize
// don't rush
// don't waste time on standings
// SOLVE THE PROBLEM OR DIE TRYING
// THE SOLUTION IS ALWAYS SIMPLE
// THE CODE IS ALWAYS SHORT
const int N = 2e5 + 5;
const int inf = 1e9;
vector<int> g[N];
int d[3][N];
bool used[N];
int sum(int v) {
return d[0][v] + d[1][v] + d[2][v];
}
void init(int n) {
for (int i = 1; i <= n; i++) {
g[i].clear();
for (int j = 0; j <= 2; j++) {
d[j][i] = inf;
}
used[i] = 0;
}
}
void bfs(int id, int s, int n) {
for (int i = 1; i <= n; i++) {
used[i] = 0;
}
d[id][s] = 0;
queue<int> q;
q.push(s);
d[id][s] = 0;
while (!q.empty()) {
int v = q.front();
q.pop();
if (used[v]) continue;
used[v] = 1;
for (int u : g[v]) {
if (used[u]) continue;
if (d[id][u] > d[id][v] + 1) {
d[id][u] = d[id][v] + 1;
q.push(u);
}
}
}
}
void Solve() {
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
init(n);
int a, b, c;
cin >> a >> b >> c;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
bfs(0, a, n);
bfs(1, b, n);
bfs(2, c, n);
int cen = 1;
for (int i = 1; i <= n; i++) {
if (sum(i) < sum(cen)) {
cen = i;
}
}
string ans;
if (cen == a) {
ans = "A";
}
else if (cen == b) {
ans = "B";
}
else if (cen == c) {
if (d[0][c] == 1) {
ans = "A";
}
else {
ans = "C";
}
}
else {
int x = d[0][cen];
int y = d[1][cen];
int z = d[2][cen];
if (x < y && z >= x - 1) {
ans = "A";
}
else if (y <= x && z >= y + 1) {
ans = "B";
}
else if (x >= z + 2 && y >= z) {
ans = "C";
}
else {
ans = "DRAW";
}
}
cout << ans << "\n";
}
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3852kb
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: 0
Accepted
time: 16ms
memory: 5740kb
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 A B A A A B B B C A A A B B DRAW C DRAW A A A A A B B A C DRAW A B A B DRAW A C DRAW A B C DRAW DRAW A A A 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 A B B B A A B B A C DRAW B A B A A A C A A DRAW A A C A DRAW C A B A...
result:
ok 10000 lines
Test #3:
score: 0
Accepted
time: 25ms
memory: 5860kb
input:
100 2000 455 1301 981 1508 1509 1242 1243 1261 1260 190 191 1981 1980 591 592 1792 1791 1726 1727 959 960 134 135 1193 1192 836 835 1803 1804 1577 1578 1548 1549 718 717 1294 1295 1116 1117 59 58 138 139 425 426 1168 1169 1963 1962 1025 1026 867 866 892 893 589 588 871 872 891 892 722 721 1711 1712 ...
output:
C A A B DRAW C A B B DRAW B C B A DRAW B C A C DRAW C B A C DRAW A C C C DRAW B A A C DRAW C A B C DRAW B A B A DRAW A C B A DRAW B C C C DRAW A B B C DRAW C B C A DRAW A C B A DRAW B A B A DRAW C A C B DRAW A B C C DRAW C B C A DRAW B A C B DRAW A A A C DRAW
result:
ok 100 lines
Test #4:
score: 0
Accepted
time: 59ms
memory: 17144kb
input:
1 200000 123236 117321 150583 47722 47723 103604 103605 48192 48191 19204 19205 3666 3667 190708 190709 111542 111541 16125 16124 164298 164299 55406 55405 62042 62041 42100 42101 40664 40663 131742 131743 105518 105517 24249 24250 174387 174388 29840 29841 164536 164537 54802 54803 6378 6377 97486 ...
output:
A
result:
ok single line: 'A'
Test #5:
score: 0
Accepted
time: 62ms
memory: 17180kb
input:
1 200000 151854 28266 141391 178840 177656 70949 127572 92675 174074 38426 55569 16718 64264 72596 171817 36908 36081 44793 65081 114199 93358 10460 36725 18563 26764 77047 29901 17769 39712 109495 141203 24130 37855 165153 135141 94225 107789 57603 49313 197306 48518 61030 57058 199291 42676 60161 ...
output:
B
result:
ok single line: 'B'
Test #6:
score: 0
Accepted
time: 52ms
memory: 17380kb
input:
1 200000 107496 54564 62204 75611 75612 33562 133562 66786 66785 35079 35078 40044 40045 99675 199675 121963 21963 15671 15672 3062 103062 71627 171627 27125 127125 30049 30048 63164 63165 183373 83373 51319 51320 99879 199879 36383 136383 89110 89109 7607 107607 20098 20099 57792 157792 100415 415 ...
output:
B
result:
ok single line: 'B'
Test #7:
score: 0
Accepted
time: 59ms
memory: 17204kb
input:
1 200000 158505 85726 178357 30247 29809 107160 107392 84411 84297 80963 81018 64893 65118 194706 194894 8253 8478 47677 48197 120341 120487 68388 68653 41048 40580 128093 127913 118156 117983 97582 97422 166508 166267 171977 171895 108683 108912 102410 102283 130584 130479 75441 75592 145257 145092...
output:
A
result:
ok single line: 'A'
Test #8:
score: 0
Accepted
time: 6ms
memory: 3684kb
input:
10992 3 1 2 3 2 1 3 1 3 1 3 2 2 1 3 1 3 2 1 3 2 1 3 1 3 2 3 1 2 1 3 1 3 3 1 2 2 1 3 1 3 3 2 1 2 1 3 1 4 1 2 3 2 1 3 2 4 1 4 1 2 4 2 1 3 2 4 1 4 1 3 2 2 1 3 2 4 1 4 1 3 4 2 1 3 2 4 1 4 1 4 2 2 1 3 2 4 1 4 1 4 3 2 1 3 2 4 1 4 2 1 3 2 1 3 2 4 1 4 2 1 4 2 1 3 2 4 1 4 2 3 1 2 1 3 2 4 1 4 2 3 4 2 1 3 2 4 ...
output:
A A B A B A B A A A A A A B A A A A A B B B C A B B A B A C A A A A A A B B A DRAW A DRAW B B A DRAW A DRAW B B A DRAW A DRAW B A A A A A A A B A A A A B B A A A A A B A A C A B B B B B C A B C A C B B A A B A A C A A A A B B A C B A C C A B B B B A A A A A A A A A A A A B B A A A A A DRAW A A DRAW ...
result:
ok 10992 lines
Test #9:
score: 0
Accepted
time: 19ms
memory: 3628kb
input:
22222 9 1 2 3 2 1 3 2 4 3 5 4 6 1 7 6 8 7 9 8 9 1 2 4 2 1 3 2 4 3 5 4 6 1 7 6 8 7 9 8 9 1 2 5 2 1 3 2 4 3 5 4 6 1 7 6 8 7 9 8 9 1 2 6 2 1 3 2 4 3 5 4 6 1 7 6 8 7 9 8 9 1 2 7 2 1 3 2 4 3 5 4 6 1 7 6 8 7 9 8 9 1 2 8 2 1 3 2 4 3 5 4 6 1 7 6 8 7 9 8 9 1 2 9 2 1 3 2 4 3 5 4 6 1 7 6 8 7 9 8 9 1 3 2 2 1 3 ...
output:
B B B A A A A A B B A A A A A C B A A A A A C C A A A A A A A A B B B A A A A A B B A A A A A C B A A A A A C C A A A B B B B A B B A A A A A A B A A A A A A C A A A A A A A A B B B A A A A C B B A A A A C C B A A A A C C C A A A B B B B B A A B B B B A A B A A A A A A A A A A A C A A A B B B C A A ...
result:
ok 22222 lines
Extra Test:
score: 0
Extra Test Passed