UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#213634#2769. 覆盖erican603772ms205372kbC++112.1kb2024-11-12 22:15:032024-11-12 23:59:35

answer

// Problem: C. 覆盖
// Contest: undefined - NOIP2024训练赛 03
// URL: http://noi.ac/contest/1155/problem/2769
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// Challenger: Erica N
// ----
// 
#include<bits/stdc++.h>

using namespace std;
#define rd read()
#define ull unsigned long long
// #define int long long 
#define pb push_back
#define itn int
#define ps second 
#define pf first


#define rd read()
int read(){
  int xx = 0, ff = 1;char ch = getchar();
  while (ch < '0' || ch > '9'){
    if (ch == '-')ff = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9')xx = xx * 10 + (ch - '0'), ch = getchar();
  return xx * ff;
}
#define zerol = 1
#ifdef zerol
#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() {cerr << endl;}
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) {
	for (auto v: a) cerr << v << ' ';err(x...);
}
template<typename T, typename... A>
void err(T a, A... x) {
	cerr << a << ' ';err(x...);
}
#else
#define dbg(...)
#endif
const int N=2e6+5;
const ull P=137;
const int INF=1e18+7;
/*

策略


*/	


vector<int> e[N];

void add(int a,int b){
	e[a].pb(b);
	e[b].pb(a);
}


bitset<N>used;
multiset<int> g[N];

void dfs(int x,int fa){
	for(auto v:e[x]){
		if(v==fa)continue;
		dfs(v,x);
		// cdbg(x,v,g[v].size());
		if(used[v]||used[x])continue;
		g[x].insert(g[v].begin(),g[v].end());
		// merge(g[v],g[x]);
		g[v].clear();
	}
	int f=0;
	// cdbg(x);
	for(auto it=g[x].begin();it!=g[x].end();){
		auto it2=it;it++;
		if(it==g[x].end()){
			
			// cdbg(*it);
			break;
		}
		// cdbg(*it2);
		if(*it==*it2){
			// cdbg(*it);
			f=1;break;
		}
	}
	
	if(f){
		// cdbg("used",x);
		g[x].clear();used[x]=1;
	}
		
	
}

signed main(){
	int n=rd;
	for(int i=1;i<n;i++){
		add(rd,rd);
	}
	
	int m=rd;	
	for(int i=1;i<=m;i++){
		int a=rd,b=rd;
		if(a==b){
			used[a]=1;
		}else{
			g[a].insert(i);
			g[b].insert(i);
		}
	}
	
	
	dfs(1,0);
	
	cout<<used.count()<<endl;
	
	for(int i=1;i<=n;i++){
		if(used[i])cout<<i<<' ';
	}
}

详细

小提示:点击横条可展开更详细的信息

Subtask #1:

score: 30
Accepted

Test #1:

score: 30
Accepted
time: 31ms
memory: 141844kb

input:

20
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
16 13
17 15
18 16
19 17
20 18
...

output:

2
3 10 

result:

ok ok

Test #2:

score: 0
Accepted
time: 16ms
memory: 141848kb

input:

20
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
16 15
17 16
18 17
19 18
20 19
...

output:

2
6 13 

result:

ok ok

Test #3:

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

input:

20
2 1
3 1
4 3
5 1
6 5
7 4
8 7
9 8
10 9
11 10
12 6
13 2
14 7
15 14
16 11
17 12
18 17
19 7
20 15
5
4 ...

output:

3
1 4 11 

result:

ok ok

Test #4:

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

input:

20
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
16 15
17 16
18 17
19 18
20 19
...

output:

2
5 11 

result:

ok ok

Test #5:

score: 0
Accepted
time: 20ms
memory: 141844kb

input:

20
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 6
10 8
11 10
12 11
13 11
14 12
15 13
16 9
17 15
18 16
19 16
20 17
1...

output:

6
1 3 7 10 17 19 

result:

ok ok

Test #6:

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

input:

20
2 1
3 2
4 3
5 3
6 5
7 4
8 6
9 8
10 7
11 7
12 10
13 12
14 13
15 9
16 14
17 16
18 16
19 17
20 15
12...

output:

3
4 9 13 

result:

ok ok

Test #7:

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

input:

20
2 1
3 1
4 2
5 3
6 4
7 5
8 6
9 7
10 8
11 9
12 10
13 11
14 10
15 14
16 10
17 13
18 4
19 18
20 4
2
1...

output:

2
5 8 

result:

ok ok

Test #8:

score: 0
Accepted
time: 28ms
memory: 141848kb

input:

20
2 1
3 2
4 3
5 4
6 5
7 4
8 7
9 6
10 9
11 8
12 11
13 10
14 10
15 12
16 14
17 13
18 17
19 14
20 18
4...

output:

2
4 10 

result:

ok ok

Test #9:

score: 0
Accepted
time: 20ms
memory: 141848kb

input:

20
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 8
12 10
13 12
14 8
15 13
16 8
17 8
18 16
19 15
20 11
12
8...

output:

3
3 8 10 

result:

ok ok

Test #10:

score: 0
Accepted
time: 32ms
memory: 141848kb

input:

20
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 7
10 9
11 10
12 8
13 11
14 12
15 13
16 14
17 15
18 16
19 18
20 19
1...

output:

2
7 12 

result:

ok ok

Subtask #2:

score: 30
Accepted

Test #11:

score: 30
Accepted
time: 36ms
memory: 141900kb

input:

1000
2 1
3 2
4 3
5 4
6 3
7 6
8 7
9 8
10 9
11 10
12 5
13 11
14 13
15 14
16 15
17 12
18 16
19 18
20 19...

output:

11
53 131 186 235 258 280 289 317 397 471 585 

result:

ok ok

Test #12:

score: 0
Accepted
time: 43ms
memory: 141908kb

input:

1000
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 12
16 14
17 16
18 17
19 18
20 1...

output:

16
96 109 110 114 152 154 179 285 315 418 463 469 526 561 610 822 

result:

ok ok

Test #13:

score: 0
Accepted
time: 35ms
memory: 141888kb

input:

1000
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
16 15
17 16
18 17
19 18
20 1...

output:

2
40 305 

result:

ok ok

Test #14:

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

input:

1000
2 1
3 2
4 3
5 4
6 4
7 5
8 6
9 7
10 8
11 9
12 11
13 10
14 12
15 14
16 13
17 15
18 16
19 17
20 18...

output:

15
36 77 111 161 164 218 236 277 281 391 408 410 460 577 738 

result:

ok ok

Test #15:

score: 0
Accepted
time: 30ms
memory: 141932kb

input:

1000
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
16 15
17 16
18 17
19 18
20 1...

output:

17
46 104 126 230 293 313 324 439 460 462 469 504 513 526 546 646 694 

result:

ok ok

Test #16:

score: 0
Accepted
time: 28ms
memory: 141888kb

input:

1000
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
16 15
17 16
18 17
19 18
20 1...

output:

6
18 114 168 201 311 651 

result:

ok ok

Test #17:

score: 0
Accepted
time: 20ms
memory: 141908kb

input:

1000
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 13
16 14
17 16
18 17
19 15
20 1...

output:

16
11 42 68 113 171 249 311 341 361 373 423 450 497 567 586 649 

result:

ok ok

Test #18:

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

input:

1000
2 1
3 2
4 3
5 4
6 5
7 6
8 6
9 8
10 9
11 7
12 11
13 10
14 12
15 13
16 15
17 14
18 15
19 18
20 16...

output:

4
15 167 387 437 

result:

ok ok

Test #19:

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

input:

1000
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
16 15
17 16
18 17
19 18
20 1...

output:

10
33 158 210 236 363 364 367 372 873 978 

result:

ok ok

Test #20:

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

input:

1000
2 1
3 2
4 3
5 4
6 5
7 6
8 3
9 8
10 9
11 10
12 11
13 7
14 12
15 13
16 7
17 14
18 17
19 15
20 16
...

output:

5
7 85 118 241 307 

result:

ok ok

Subtask #3:

score: 0
Time Limit Exceeded

Test #21:

score: 40
Accepted
time: 1235ms
memory: 205336kb

input:

2000000
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 11
15 14
16 13
17 15
18 16
19 17
2...

output:

5
260 10715 16698 23494 49620 

result:

ok ok

Test #22:

score: 0
Accepted
time: 2007ms
memory: 205372kb

input:

2000000
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
16 15
17 16
18 17
19 18
2...

output:

45
2404 7524 11229 11999 14383 16080 18852 24573 25801 31547 35420 37754 42334 58888 69242 72415 820...

result:

ok ok

Test #23:

score: -40
Time Limit Exceeded

input:

2000000
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
16 15
17 16
18 17
19 18
2...

output:


result: