QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#258263#2272. Formica SokobanicaFireball0424#WA 47ms58304kbC++141.8kb2023-11-19 16:33:032023-11-19 16:33:04

Judging History

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

  • [2023-11-19 16:33:04]
  • 评测
  • 测评结果:WA
  • 用时:47ms
  • 内存:58304kb
  • [2023-11-19 16:33:03]
  • 提交

answer

#pragma GCC optimizer("Ofast")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
#define int long long 
#define ld long double
#define ull unsigned long long 
#define fr first
#define fi first
#define sc second
#define se second
#define all(x) x.begin(), x.end()
#define pii pair<int,int>
using namespace std;

#ifndef fireball
#define tofu ios::sync_with_stdio(0); cin.tie(0);
#else
#define tofu freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#endif 

void db() {cout << '\n';}
template <typename T, typename ...U> void db(T a, U ...b) {cout << a << ' ', db(b...);}

signed main(){
    tofu;

    int n, m;
    cin >> n >> m;
    vector<int> g[n + 1];
    for(int i = 1; i < n; ++i){
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    int a[n + 1] = {};
    for(int i = 0; i < m; ++i){
        int x; cin >> x;
        a[x] = 1;
    }

    int vis[n + 1] = {};
    function<void(int,int, int)> dfs = [&](int u, int pa, int f){
        vis[pa] = 1;
        if(g[u].size() == 1){
            if(f == 0) vis[u] = 1;
            return;
        }

        int has = 0;
        for(int i : g[u]) if(i != pa and !a[i]) has++;
        for(int i : g[u]){
            if(i == pa) continue;
            if(a[i]){
                if(f == 0) dfs(i, u, 1);
                else if(has) dfs(i, u, 1);
            }
            else{
                if(has > 1) dfs(i, u, 0);
                else dfs(i, u, f);
            }
        }
    };

    for(int i : g[1]){
        if(a[i]) dfs(i, 1, 1);
        else dfs(i, 1, 0);
    }

    //for(int i = 1; i <= n; ++i) db(i, vis[i]);

    int ans = 0;
    for(int i = 1; i <= n; ++i) ans += vis[i];
    db(ans);
}

详细

Test #1:

score: 100
Accepted
time: 35ms
memory: 19008kb

input:

200000 67431
1 134415
1 3
1 4
11 1
13 1
19 1
1 25
31 1
1 33
41 1
46 1
48 1
1 52
1 55
60 1
63 1
1 77
78 1
85 1
1 86
1 87
90 1
92 1
95 1
1 96
1 98
1 103
1 115
1 123
1 126
1 128
1 130
137 1
140 1
141 1
1 142
153 1
162 1
165 1
167 1
1 169
1 170
177 1
1 187
1 189
1 190
1 193
1 197
202 1
1 216
1 220
1 222...

output:

132569 

result:

ok single line: '132569 '

Test #2:

score: 0
Accepted
time: 27ms
memory: 18992kb

input:

200000 66498
1 50279
1 213
1 218
220 1
1 224
1 229
1 232
1 236
239 1
1 240
1 244
246 1
247 1
1 255
1 257
1 260
271 1
276 1
278 1
1 280
282 1
1 288
292 1
293 1
300 1
1 303
1 309
1 312
1 317
321 1
322 1
326 1
327 1
328 1
340 1
342 1
346 1
1 352
1 363
366 1
368 1
370 1
374 1
382 1
384 1
1 389
1 392
393...

output:

133502 

result:

ok single line: '133502 '

Test #3:

score: 0
Accepted
time: 47ms
memory: 58304kb

input:

200000 1
395 397
792 125000
792 796
797 798
800 799
801 800
803 805
807 805
807 808
809 808
812 813
818 816
820 821
821 822
825 826
826 829
829 831
831 832
833 836
836 839
840 839
841 840
842 844
847 845
851 849
851 853
871 872
873 875
878 875
881 879
886 887
894 895
900 897
901 903
908 909
911 909
...

output:

199999 

result:

ok single line: '199999 '

Test #4:

score: 0
Accepted
time: 44ms
memory: 58292kb

input:

200000 0
80643 20559
100001 3
3 4
7 6
7 9
10 9
10 11
11 14
23 24
25 24
27 26
28 27
33 31
38 39
40 39
41 40
41 42
45 42
45 46
47 46
47 49
50 49
51 50
51 53
54 53
54 57
58 57
58 59
61 59
63 66
68 66
71 70
71 73
73 78
78 79
85 82
91 89
95 94
95 97
97 98
101 103
104 109
110 111
114 111
117 114
127 126
1...

output:

200000 

result:

ok single line: '200000 '

Test #5:

score: -100
Wrong Answer
time: 0ms
memory: 3612kb

input:

1 0

output:

0 

result:

wrong answer 1st lines differ - expected: '1', found: '0 '