QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#414111#7986. 游戏AcetaminophenAC ✓24ms17704kbC++111004b2024-05-18 15:26:322024-05-18 15:26:33

Judging History

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

  • [2024-05-18 15:26:33]
  • 评测
  • 测评结果:AC
  • 用时:24ms
  • 内存:17704kb
  • [2024-05-18 15:26:32]
  • 提交

answer

#include <iostream>
#include <vector>
#include <cstdio>
#define ll long long
#define MAXN (ll) 1e5+5
using namespace std;

ll avail[MAXN];
vector<ll> v[MAXN];

void dfs(ll now = 1, ll fa = -1)
{
    ll nowavail = 0;
    for(auto &i : v[now])
    {
        if(i != fa)
        {
            dfs(i, now);
            nowavail += avail[i] > 1 || v[i].size() == 1;
        }
    }
    if(v[now].size() == 1)
        nowavail ++;
    avail[now] = nowavail;
}

void dfsans(ll now = 1, ll fa = -1)
{
    if(v[now].size() == 1)
    {
        cout << "You win, temporarily.";
        exit(0);
    }
    if(avail[now] <= 1)
        return;
    for(auto &i : v[now])
        if(i != fa)
            dfsans(i, now);
}

int main()
{
    ll n;
    scanf("%lld",&n);
    for(int i = 1; i < n; i++)
    {
        ll a, b;
        scanf("%lld%lld", &a, &b);
        v[a].push_back(b);
        v[b].push_back(a);
    }
    dfs();
    dfsans();
    cout << "Wasted.";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 5996kb

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: 0
Accepted
time: 1ms
memory: 6108kb

input:

1

output:

Wasted.

result:

ok single line: 'Wasted.'

Test #4:

score: 0
Accepted
time: 18ms
memory: 10656kb

input:

100000
86389 1
68115 86389
27661 68115
9669 27661
7343 9669
59420 7343
98078 59420
39321 98078
14847 39321
76863 14847
21104 14847
24241 39321
82708 39321
73282 82708
7424 39321
64358 7424
81481 39321
17105 81481
74205 17105
81202 98078
63636 81202
62429 63636
85827 62429
8648 62429
67963 63636
7287...

output:

You win, temporarily.

result:

ok single line: 'You win, temporarily.'

Test #5:

score: 0
Accepted
time: 24ms
memory: 10452kb

input:

100000
28424 1
91124 28424
70268 91124
99456 70268
80696 99456
72802 80696
69700 72802
77527 72802
3835 80696
83715 3835
6690 3835
63240 3835
87789 80696
29903 99456
21234 29903
92544 21234
87569 21234
67361 29903
18146 67361
22916 67361
7024 99456
62805 7024
24624 7024
37895 7024
29126 99456
13746 ...

output:

Wasted.

result:

ok single line: 'Wasted.'

Test #6:

score: 0
Accepted
time: 21ms
memory: 10484kb

input:

100000
40385 1
28939 40385
71739 28939
66436 71739
29540 66436
79210 29540
60766 29540
68309 66436
69492 68309
21819 68309
57705 71739
33098 57705
54050 33098
19349 33098
98912 33098
20261 57705
72108 71739
49433 72108
87548 49433
78576 49433
29257 49433
39468 72108
44720 39468
87329 39468
82036 721...

output:

You win, temporarily.

result:

ok single line: 'You win, temporarily.'

Test #7:

score: 0
Accepted
time: 21ms
memory: 10564kb

input:

100000
56256 1
19611 56256
63814 19611
13211 63814
40727 13211
15422 13211
41472 63814
61111 41472
41205 41472
7343 41472
4246 63814
61460 4246
47333 61460
6130 61460
76912 4246
95893 63814
4861 95893
32371 95893
53124 95893
87414 63814
83500 63814
89982 83500
26326 89982
50802 89982
15280 89982
584...

output:

Wasted.

result:

ok single line: 'Wasted.'

Test #8:

score: 0
Accepted
time: 21ms
memory: 10468kb

input:

100000
53790 1
72385 53790
72398 72385
89902 72398
52488 89902
46763 89902
33914 72398
31021 33914
7197 33914
6377 72398
67336 6377
81807 6377
28285 72398
66168 28285
72743 28285
78065 72398
51875 78065
50576 78065
91812 72398
91740 91812
31634 91812
47708 72398
63776 47708
95702 47708
43401 47708
6...

output:

You win, temporarily.

result:

ok single line: 'You win, temporarily.'

Test #9:

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

input:

2
2 1

output:

You win, temporarily.

result:

ok single line: 'You win, temporarily.'

Test #10:

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

input:

3
3 1
2 1

output:

You win, temporarily.

result:

ok single line: 'You win, temporarily.'

Test #11:

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

input:

5
2 1
5 1
4 2
3 5

output:

Wasted.

result:

ok single line: 'Wasted.'

Test #12:

score: 0
Accepted
time: 21ms
memory: 14924kb

input:

100000
95951 1
87803 95951
87786 87803
1967 87786
63511 1967
77383 63511
71246 77383
44818 71246
33021 44818
73494 33021
58093 73494
40174 58093
8359 40174
11144 8359
29236 11144
37628 29236
29240 37628
21048 29240
53805 21048
99785 53805
25492 99785
37728 25492
69992 37728
85330 69992
82016 85330
4...

output:

Wasted.

result:

ok single line: 'Wasted.'

Test #13:

score: 0
Accepted
time: 15ms
memory: 17704kb

input:

100000
92446 1
74229 92446
27345 74229
4264 27345
61335 4264
43841 61335
60690 43841
10849 60690
56364 10849
74376 56364
71293 74376
3042 71293
60707 3042
51718 60707
19196 51718
51611 19196
99638 51611
51205 99638
11710 51205
70549 11710
86878 70549
86137 86878
99799 86137
42869 99799
5001 42869
61...

output:

You win, temporarily.

result:

ok single line: 'You win, temporarily.'

Test #14:

score: 0
Accepted
time: 19ms
memory: 10596kb

input:

100000
75730 1
73800 75730
12806 73800
77106 12806
91392 77106
44200 91392
61777 44200
11844 61777
84247 11844
34740 84247
96676 34740
53745 96676
76538 53745
4699 76538
93802 4699
23312 93802
1193 93802
82164 4699
90396 76538
26070 90396
81104 26070
94136 26070
55901 90396
95752 53745
73831 95752
4...

output:

Wasted.

result:

ok single line: 'Wasted.'

Test #15:

score: 0
Accepted
time: 18ms
memory: 10604kb

input:

100000
5379 1
4362 5379
25328 4362
83655 25328
45527 83655
78313 45527
81689 78313
60981 81689
95857 60981
75786 95857
68680 75786
49056 68680
88964 49056
74842 88964
52254 74842
88910 52254
29774 88910
72092 29774
74298 29774
37594 88910
58022 37594
83462 37594
27150 37594
32459 52254
71699 32459
4...

output:

You win, temporarily.

result:

ok single line: 'You win, temporarily.'

Test #16:

score: 0
Accepted
time: 23ms
memory: 10556kb

input:

100000
99 1
87173 99
69795 87173
16946 69795
17139 16946
21699 17139
5947 21699
63438 5947
77592 63438
59991 63438
75630 63438
82612 5947
37096 21699
58531 37096
9180 58531
49513 58531
67478 37096
37690 21699
69575 37690
73694 69575
27670 73694
3136 69575
22066 3136
65930 37690
31007 65930
18242 216...

output:

Wasted.

result:

ok single line: 'Wasted.'