QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#543074#7786. Graft and TransplantMaxDYFWA 2ms8964kbC++141.2kb2024-09-01 13:32:442024-09-01 13:32:45

Judging History

This is the latest submission verdict.

  • [2024-09-01 13:32:45]
  • Judged
  • Verdict: WA
  • Time: 2ms
  • Memory: 8964kb
  • [2024-09-01 13:32:44]
  • 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 ? "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: 2ms
memory: 8520kb

input:

4
1 2
2 3
3 4

output:

Alice

result:

ok "Alice"

Test #2:

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

input:

4
1 2
1 3
1 4

output:

Bob

result:

ok "Bob"

Test #3:

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

input:

2
1 2

output:

Alice

result:

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