QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#738677#2272. Formica SokobanicaShuishuiWA 57ms40140kbC++141.4kb2024-11-12 19:41:432024-11-12 19:41:45

Judging History

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

  • [2024-11-12 19:41:45]
  • 评测
  • 测评结果:WA
  • 用时:57ms
  • 内存:40140kb
  • [2024-11-12 19:41:43]
  • 提交

answer

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

#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define Sz(x) (int)(x).size()
#define bit(x) (1ll << (x))
using ll = long long;
using db = double;
using ull = unsigned long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vii = vector<vi>;
using vl = vector<ll>;
using vll = vector<vl>;
using vs = vector<string>;
using vd = vector<db>;
mt19937 mrand(time(0));

void solve(void)
{
	int n, m;
	cin >> n >> m;
	vii e(n + 2);
	for (int i = 1; i < n; i++)
	{
		int u, v;
		cin >> u >> v;
		e[u].pb(v);
		e[v].pb(u);
	}

	vi a(n + 2);
	for (int i = 1; i <= m; i++)
	{
		int x;
		cin >> x;
		a[x] = 1;
	}

	int ans = 0;
	function<void(int, int, int)> dfs = [&](int u, int fa, int tp)
	{
		
		a[u] |= tp;
		int cnt = 0;
		for (auto v : e[u]) if (v != fa)
			if (a[v] == 0)
				cnt++;

		if (cnt || !a[u]) ans++;
		// cerr << u << " " << cnt << "\n";
		for (auto v : e[u]) if (v != fa)
		{
			cnt -= (a[v] == 0);
			if (cnt >= 1)
				dfs(v, u, 0);
			else
			{
				if (!(a[v] && a[u]))
					dfs(v, u, a[u]);
			}
			cnt += (a[v] == 0);
		}
	};
	dfs(1, 0, 0);
	cout << ans << "\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	// cout << fixed << setprecision(10);

	int T = 1;
	// cin >> T;
	for (int i = 1; i <= T; i++)
	solve();

	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 28ms
memory: 15808kb

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: 30ms
memory: 15812kb

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: 44ms
memory: 40140kb

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: 48ms
memory: 39976kb

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

input:

1 0

output:

1

result:

ok single line: '1'

Test #6:

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

input:

2 0
2 1

output:

2

result:

ok single line: '2'

Test #7:

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

input:

2 1
2 1
2

output:

1

result:

ok single line: '1'

Test #8:

score: -100
Wrong Answer
time: 57ms
memory: 14996kb

input:

200000 66659
199145 199147
1 982
995 1
1021 1
1141 1
1 4370
1 21842
1 31917
67858 1
1 6658
106770 1
1 176182
1 92830
176182 82908
163205 151261
163205 69945
25981 151261
84701 151261
133323 25981
3569 67662
144579 102158
51901 136200
39443 51901
39443 105504
188083 73666
160799 73666
110052 44678
31...

output:

115134

result:

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