QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#244147#2272. Formica SokobanicaNYCU_gAwr_gurA#WA 31ms15804kbC++171.2kb2023-11-08 21:34:562023-11-08 21:34:58

Judging History

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

  • [2023-11-08 21:34:58]
  • 评测
  • 测评结果:WA
  • 用时:31ms
  • 内存:15804kb
  • [2023-11-08 21:34:56]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#define fast
#else
#define fast cin.tie(0)->sync_with_stdio(0)
#define cerr if(1);else cerr
#define endl '\n'
#endif
#define _ <<' '<<
#define ALL(v) v.begin(),v.end()
#define ft first
#define sd second

using ll = long long;
using ld = long double;
using pii = pair<int,int>;

const int maxn = 2e5+50;
vector<int> G[maxn];
int has[maxn];

int ans = 0;

void dfs(int cur, int fa, bool gg) {
    if (has[cur] && gg) return;

    int can = 0;
    for (int &nxt : G[cur]) {
        if (nxt == fa) continue;
        can += !has[nxt];
    }

    if (can || !gg) {
        cerr << "can : " << cur << endl;
        ++ans;
    }

    gg |= has[cur];
    
    for (int &nxt : G[cur]) {
        if (nxt != fa) {
            if ((can - !has[nxt])) dfs(nxt, cur, 0);
            else dfs(nxt, cur, gg);
        }
    }
}


signed main() {
    fast;

    int n, k;
    cin >> n >> k;
    for (int i = 1; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    for (int i = 0; i < k; ++i) {
        int x; cin >> x;
        has[x] = 1;
    }

    dfs(1,1,0);

    cout << ans << endl;

    cerr _ "meow" _ endl;

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 31ms
memory: 15804kb

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:

200000

result:

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