QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#414051#7986. 游戏aurorawhiteseaWA 1ms7680kbC++141.7kb2024-05-18 14:41:002024-05-18 14:41:01

Judging History

你现在查看的是最新测评结果

  • [2024-05-18 14:41:01]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:7680kb
  • [2024-05-18 14:41:00]
  • 提交

answer

#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <numeric>
using namespace std;
typedef long long ll;
int head[100005], cnt, n, l, r, dep[100005], dep1[100005], num[100005];
bool off[100005];
vector<int>v[100005];

bool cmp1(int a, int b)
{
    if (dep1[a] != dep1[b])
        return dep1[a] < dep1[b];
    else return num[a] > num[b];
}
struct tree
{
    int to;
    int next;
}c[100005];
void add(int a, int b)
{
    v[a].push_back(b);
}
int dfs1(int x)
{
    if (v[x].size() == 0)dep1[x] = 1;
    for (int i = 0; i<v[x].size(); i++)
    {
        dep1[x] = min(dep1[x], dfs1(v[x][i])+ 1);
    }
    return dep1[x];
}
int dfs(int x)
{
    if (v[x].size() == 0)
    {
        num[x] = 1;
        return 1;
    }
    for (int i = 0; i < v[x].size(); i++)
    {
        if (dep1[v[x][i]] + 1 == dep1[x])
        {
            num[x] += dfs(v[x][i]);
        }
    }
    return num[x];
}
bool f(int x)
{
    if (dep1[x] == 1)
        return true;
    if (v[x].size() < 2)
        return false;
    sort(v[x].begin(), v[x].end(), cmp1);
    return f(v[x][1]);
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        dep1[i] = 0x3f3f3f3f;
    }
    for (int i = 1; i <= n - 1; i++)
    {
        cin >> l >> r;
        add(l, r);
    }
    dfs1(1);
    dfs(1);
    bool ff = f(1);
    if (ff)
    {
        cout << "You win, temporarily." << endl;
    }
    else
    {
        cout << "Wasted." << endl;
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 7680kb

input:

6
1 2
2 3
2 4
1 5
5 6

output:

Wasted.

result:

ok single line: 'Wasted.'

Test #2:

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

input:

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

output:

You win, temporarily.

result:

ok single line: 'You win, temporarily.'

Test #3:

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

input:

1

output:

You win, temporarily.

result:

wrong answer 1st lines differ - expected: 'Wasted.', found: 'You win, temporarily.'