QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#847772#9996. 辞甲猾扎guleng2007AC ✓642ms97672kbC++201.0kb2025-01-08 11:04:252025-01-08 11:04:25

Judging History

This is the latest submission verdict.

  • [2025-01-08 11:04:25]
  • Judged
  • Verdict: AC
  • Time: 642ms
  • Memory: 97672kb
  • [2025-01-08 11:04:25]
  • Submitted

answer

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

const int N=1e6+5;

vector <int> g[N];
int fa[N];

void dfs1(int x)
{
	for(auto to:g[x])
		if(to!=fa[x])
			fa[to]=x, dfs1(to);
}

bool need[N], up[N], key[N], col[N];
int ans;

void dfs2(int x)
{
	for(auto to:g[x])
		if(to!=fa[x])
			dfs2(to);

	if(key[x])
	{
		for(auto to:g[x])
			if(to!=fa[x] && need[to])
				ans++;
		return;
	}

	for(auto to:g[x])
		if(to!=fa[x] && need[to])
		{
			up[x]=true, ans++;
			break;
		}

	if(up[x])
		return;

	if(!col[x])
		return;

	need[x]=true;
	for(auto to:g[x])
		if(to!=fa[x] && up[to])
			need[x]=false;
}

int main()
{
	int n,k;
	cin >> n >> k;
	for(int i=1;i<=k;i++)
	{
		int id;
		scanf("%d",&id);
		key[id]=true;
	}

	for(int i=1;i<n;i++)
	{
		int x,y;
		scanf("%d %d",&x,&y);
		g[x].push_back(y);
		g[y].push_back(x);
	}

	for(int i=1;i<=n;i++)
		if(key[i])
			for(auto to:g[i])
				col[to]=true;

	dfs1(1);
	dfs2(1);

	if(need[1])
		ans++;

	printf("%d\n",ans);
	return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 601ms
memory: 66532kb

input:

1000000 250
4246 6001 15765 16292 18291 18607 20931 24218 25916 28742 34837 37283 38797 38805 45707 47625 47981 55382 60377 60815 61528 71455 73316 79270 81165 88222 93488 95638 99798 100415 100686 107252 107624 110367 116459 118365 121070 130962 131316 132856 141146 152992 153050 154652 156855 1669...

output:

497

result:

ok single line: '497'

Test #2:

score: 0
Accepted
time: 630ms
memory: 66880kb

input:

1000000 200000
9 11 14 17 27 43 45 51 54 56 65 68 69 79 80 81 83 100 104 111 112 113 118 119 121 122 126 140 141 142 144 148 152 156 159 160 161 175 180 181 187 188 189 194 196 208 219 237 242 243 245 247 250 254 255 272 286 291 297 302 307 310 312 316 317 324 325 326 327 330 334 340 350 357 358 361...

output:

216049

result:

ok single line: '216049'

Test #3:

score: 0
Accepted
time: 642ms
memory: 66872kb

input:

1000000 600000
2 3 5 6 7 8 9 11 12 13 14 17 19 20 21 22 23 24 26 27 28 30 31 32 34 35 37 38 39 42 43 49 50 52 54 56 58 59 60 61 63 65 68 69 71 73 74 75 76 81 84 85 86 89 90 91 92 94 95 96 98 100 101 102 103 105 107 108 109 110 111 115 117 119 122 126 127 131 134 135 140 141 143 144 145 146 147 148 1...

output:

250733

result:

ok single line: '250733'

Test #4:

score: 0
Accepted
time: 266ms
memory: 67404kb

input:

1000000 456531
1 4 5 6 11 12 15 16 19 21 28 29 30 31 34 35 36 39 40 42 45 49 51 54 58 61 62 63 67 71 72 73 74 76 78 79 81 83 86 87 88 90 91 92 95 96 98 101 102 108 114 116 119 120 121 127 129 134 138 140 143 148 149 157 161 164 168 169 170 174 177 179 180 186 191 192 194 196 198 199 201 205 206 207 ...

output:

275656

result:

ok single line: '275656'

Test #5:

score: 0
Accepted
time: 159ms
memory: 46696kb

input:

600000 300083
1 3 8 10 11 14 18 21 27 28 32 33 35 36 38 41 42 45 47 48 51 52 54 55 58 59 62 64 66 68 69 71 72 73 77 78 79 87 89 92 98 100 101 103 108 109 112 113 114 115 118 120 122 126 128 130 132 133 134 135 139 140 141 143 144 145 146 147 151 153 154 155 157 160 161 162 164 165 168 172 174 176 17...

output:

168618

result:

ok single line: '168618'

Test #6:

score: 0
Accepted
time: 160ms
memory: 43720kb

input:

600000 299851
10 11 12 16 18 19 20 27 28 29 32 39 45 46 47 50 51 52 54 56 58 59 60 61 63 66 67 68 70 71 72 73 74 75 76 77 78 80 81 82 84 85 87 91 92 93 95 99 106 107 108 109 110 113 114 116 117 118 119 120 121 123 126 127 128 131 132 133 134 135 137 139 143 144 148 149 150 151 153 154 156 157 160 16...

output:

163002

result:

ok single line: '163002'

Test #7:

score: 0
Accepted
time: 169ms
memory: 66608kb

input:

1000000 1414
1 3 6 10 15 21 28 36 45 55 66 78 91 105 120 136 153 171 190 210 231 253 276 300 325 351 378 406 435 465 496 528 561 595 630 666 703 741 780 820 861 903 946 990 1035 1081 1128 1176 1225 1275 1326 1378 1431 1485 1540 1596 1653 1711 1770 1830 1891 1953 2016 2080 2145 2211 2278 2346 2415 24...

output:

1412

result:

ok single line: '1412'

Test #8:

score: 0
Accepted
time: 641ms
memory: 66908kb

input:

1000000 407091
5 6 7 8 9 16 22 25 26 27 28 29 30 31 32 38 39 44 45 48 49 54 60 61 62 67 69 74 75 76 83 89 90 93 96 100 104 106 107 108 111 112 113 115 117 119 123 124 127 131 133 137 138 139 140 141 148 151 152 153 164 166 168 169 174 178 179 184 189 190 191 192 193 195 196 198 199 201 207 208 209 2...

output:

190450

result:

ok single line: '190450'

Test #9:

score: 0
Accepted
time: 632ms
memory: 66916kb

input:

1000000 203539
2 5 7 9 17 19 24 27 28 29 33 36 39 48 55 61 62 63 65 66 74 77 84 88 93 94 109 122 124 125 131 133 138 156 157 168 171 175 182 206 217 219 220 223 224 225 235 237 243 245 246 250 251 252 261 267 268 273 274 276 284 287 294 299 303 315 316 320 333 339 341 356 363 367 369 375 378 383 401...

output:

126720

result:

ok single line: '126720'

Test #10:

score: 0
Accepted
time: 182ms
memory: 71472kb

input:

1000000 60
17851 75097 79152 97364 119531 131926 139261 143508 148642 174210 189088 192588 196317 223788 226557 239203 241237 257958 282905 287627 322019 328596 336682 349655 390042 430078 433655 446727 460614 469941 470717 490665 525808 549719 554867 558559 598840 605288 650172 651324 659016 700548...

output:

120

result:

ok single line: '120'

Test #11:

score: 0
Accepted
time: 188ms
memory: 67748kb

input:

1000000 44
3924 64080 87781 91306 131716 139380 148096 165450 177668 186165 189451 208312 289142 314273 320868 323509 338675 347529 348420 359087 379263 380354 394605 451132 467069 482609 519200 584980 586564 597544 604605 610043 639050 643219 695547 708158 723610 748175 786562 789197 868808 907058 ...

output:

89

result:

ok single line: '89'

Test #12:

score: 0
Accepted
time: 184ms
memory: 97672kb

input:

1000000 1200
126 1011 1363 1600 2821 2847 4573 5673 5805 6708 6837 6935 8092 8287 9294 10728 11223 11926 12145 12506 13474 14386 14392 15769 18045 18466 19417 19680 20811 21433 21629 21817 22403 22434 22489 24898 26697 26783 28843 30383 30789 30867 31296 31345 32403 33070 33281 33757 34216 37784 379...

output:

2391

result:

ok single line: '2391'