QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#543076#7786. Graft and TransplantMaxDYFWA 2ms9764kbC++141.2kb2024-09-01 13:33:472024-09-01 13:33:47

Judging History

This is the latest submission verdict.

  • [2024-09-01 13:33:47]
  • Judged
  • Verdict: WA
  • Time: 2ms
  • Memory: 9764kb
  • [2024-09-01 13:33:47]
  • Submitted

answer


// #pragma GCC optimize("Ofast,no-stack-protector")
#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;
const int inf = 1 << 30;
const long long llinf = 1ll << 60;
const double PI = acos(-1);

#define lowbit(x) (x & -x)
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<db, db> pdd;
typedef pair<ll, int> pli;

int n, m, k, q;
int d = 0;
int d1[N], d2[N];
vector<int> E[N];

void dfs(int u, int fa)
{
    d1[u] = d2[u] = 0;
    for (int v : E[u])
    {
        if (v == fa)
            continue;
        dfs(v, u);
        int t = d1[v] + 1;
        if (t > d1[u])
            d2[u] = d1[u], d1[u] = t;
        else if (t > d2[u])
            d2[u] = t;
    }
    d = max(d, d1[u] + d2[u]);
}
void work()
{
    cin >> n;
    for (int i = 1; i < n; i++)
    {
        int x, y;
        cin >> x >> y;
        E[x].push_back(y);
        E[y].push_back(x);
    }
    dfs(1, 0);
    cout << ((d % 2 == 0 || d == 1) ? "Bob\n" : "Alice\n");
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    while (t-- > 0)
    {
        work();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 8320kb

input:

4
1 2
2 3
3 4

output:

Alice

result:

ok "Alice"

Test #2:

score: 0
Accepted
time: 1ms
memory: 8908kb

input:

4
1 2
1 3
1 4

output:

Bob

result:

ok "Bob"

Test #3:

score: 0
Accepted
time: 2ms
memory: 9716kb

input:

2
1 2

output:

Bob

result:

ok "Bob"

Test #4:

score: 0
Accepted
time: 0ms
memory: 9296kb

input:

3
1 2
1 3

output:

Bob

result:

ok "Bob"

Test #5:

score: 0
Accepted
time: 1ms
memory: 8340kb

input:

5
2 1
2 3
3 4
1 5

output:

Bob

result:

ok "Bob"

Test #6:

score: 0
Accepted
time: 1ms
memory: 9764kb

input:

6
4 3
4 2
4 5
4 1
4 6

output:

Bob

result:

ok "Bob"

Test #7:

score: 0
Accepted
time: 0ms
memory: 9300kb

input:

7
2 4
4 1
1 5
5 3
3 7
7 6

output:

Bob

result:

ok "Bob"

Test #8:

score: 0
Accepted
time: 0ms
memory: 8316kb

input:

8
2 3
3 1
3 6
7 6
6 5
7 8
6 4

output:

Bob

result:

ok "Bob"

Test #9:

score: -100
Wrong Answer
time: 1ms
memory: 9096kb

input:

9
1 3
1 4
4 2
3 7
5 7
5 6
1 9
9 8

output:

Bob

result:

wrong answer 1st words differ - expected: 'Alice', found: 'Bob'