답안 #949932

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
949932	2024-03-19T23:14:15 Z	Saul0906	Hotspot (NOI17_hotspot)	C++14	38 / 100	7 ms	16312 KB

hotspot

#include <bits/stdc++.h>
#define rep(a,b,c) for(int a=b; a<c; a++)
#define repa(a,b) for(auto a: b)
#define pb push_back

using namespace std;

const int lim=5e5+5;
vector<int> ady[lim];
int cont[lim]{}, par[lim]{}, lvl[lim]{};
bool vis[lim]{};

void solve(int u, int v){
	if(lvl[u]<lvl[v]) swap(u,v);
	while(lvl[u]>lvl[v]){
		cont[u]++;
		u=par[u];
	}
	while(u!=v){
		cont[u]++;
		cont[v]++;
		u=par[u];
		v=par[v];
	}
	cont[u]++;
}

void dfs(int u, int p){
	vis[u]=true;
	par[u]=p;
	if(p!=-1) lvl[u]=lvl[p]+1;
	repa(v,ady[u]) if(!vis[v]) dfs(v,u);
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n, m, k, u, v;
	cin>>n>>m;
	rep(i,0,m){
		cin>>u>>v;
		ady[u].pb(v);
		ady[v].pb(u);
	}
	dfs(0,-1);
	cin>>k;
	rep(i,0,k){
		cin>>u>>v;
		solve(u,v);
	}
	u=0;
	rep(i,0,lim) if(cont[u]<cont[i]) u=i;
	cout<<u<<endl;
}

Subtask #1

4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	16216 KB	Output is correct
2	Correct	5 ms	16220 KB	Output is correct
3	Correct	6 ms	16220 KB	Output is correct
4	Correct	6 ms	16220 KB	Output is correct
5	Correct	5 ms	16220 KB	Output is correct
6	Correct	5 ms	16220 KB	Output is correct
7	Correct	5 ms	16220 KB	Output is correct

Subtask #2

5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	16216 KB	Output is correct
2	Correct	5 ms	16220 KB	Output is correct
3	Correct	6 ms	16220 KB	Output is correct
4	Correct	6 ms	16220 KB	Output is correct
5	Correct	5 ms	16220 KB	Output is correct
6	Correct	5 ms	16220 KB	Output is correct
7	Correct	5 ms	16220 KB	Output is correct
8	Correct	5 ms	16220 KB	Output is correct
9	Correct	5 ms	16220 KB	Output is correct
10	Correct	5 ms	16220 KB	Output is correct
11	Correct	5 ms	16220 KB	Output is correct
12	Correct	5 ms	16220 KB	Output is correct
13	Correct	6 ms	16220 KB	Output is correct
14	Correct	5 ms	16312 KB	Output is correct

Subtask #3

11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	16216 KB	Output is correct
2	Correct	5 ms	16220 KB	Output is correct
3	Correct	6 ms	16220 KB	Output is correct
4	Correct	6 ms	16220 KB	Output is correct
5	Correct	5 ms	16220 KB	Output is correct
6	Correct	5 ms	16220 KB	Output is correct
7	Correct	5 ms	16220 KB	Output is correct
8	Correct	5 ms	16216 KB	Output is correct
9	Correct	5 ms	16220 KB	Output is correct
10	Correct	5 ms	16220 KB	Output is correct
11	Correct	6 ms	16220 KB	Output is correct
12	Correct	5 ms	16220 KB	Output is correct
13	Correct	5 ms	16220 KB	Output is correct
14	Correct	5 ms	16220 KB	Output is correct

Subtask #4

18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	16216 KB	Output is correct
2	Correct	5 ms	16220 KB	Output is correct
3	Correct	6 ms	16220 KB	Output is correct
4	Correct	6 ms	16220 KB	Output is correct
5	Correct	5 ms	16220 KB	Output is correct
6	Correct	5 ms	16220 KB	Output is correct
7	Correct	5 ms	16220 KB	Output is correct
8	Correct	5 ms	16220 KB	Output is correct
9	Correct	5 ms	16220 KB	Output is correct
10	Correct	5 ms	16220 KB	Output is correct
11	Correct	5 ms	16220 KB	Output is correct
12	Correct	5 ms	16220 KB	Output is correct
13	Correct	6 ms	16220 KB	Output is correct
14	Correct	5 ms	16312 KB	Output is correct
15	Correct	5 ms	16216 KB	Output is correct
16	Correct	5 ms	16220 KB	Output is correct
17	Correct	5 ms	16220 KB	Output is correct
18	Correct	6 ms	16220 KB	Output is correct
19	Correct	5 ms	16220 KB	Output is correct
20	Correct	5 ms	16220 KB	Output is correct
21	Correct	5 ms	16220 KB	Output is correct
22	Correct	5 ms	16220 KB	Output is correct
23	Correct	5 ms	16220 KB	Output is correct
24	Correct	5 ms	16220 KB	Output is correct
25	Correct	5 ms	16220 KB	Output is correct
26	Correct	7 ms	16220 KB	Output is correct
27	Correct	6 ms	16220 KB	Output is correct
28	Correct	5 ms	16220 KB	Output is correct

Subtask #5

0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	16216 KB	Output is correct
2	Correct	5 ms	16220 KB	Output is correct
3	Correct	6 ms	16220 KB	Output is correct
4	Correct	6 ms	16220 KB	Output is correct
5	Correct	5 ms	16220 KB	Output is correct
6	Correct	5 ms	16220 KB	Output is correct
7	Correct	5 ms	16220 KB	Output is correct
8	Correct	5 ms	16220 KB	Output is correct
9	Correct	5 ms	16220 KB	Output is correct
10	Correct	5 ms	16220 KB	Output is correct
11	Correct	5 ms	16220 KB	Output is correct
12	Correct	5 ms	16220 KB	Output is correct
13	Correct	6 ms	16220 KB	Output is correct
14	Correct	5 ms	16312 KB	Output is correct
15	Incorrect	6 ms	16216 KB	Output isn't correct
16	Halted	0 ms	0 KB	-

Subtask #6

0 / 36.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	16216 KB	Output is correct
2	Correct	5 ms	16220 KB	Output is correct
3	Correct	6 ms	16220 KB	Output is correct
4	Correct	6 ms	16220 KB	Output is correct
5	Correct	5 ms	16220 KB	Output is correct
6	Correct	5 ms	16220 KB	Output is correct
7	Correct	5 ms	16220 KB	Output is correct
8	Correct	5 ms	16220 KB	Output is correct
9	Correct	5 ms	16220 KB	Output is correct
10	Correct	5 ms	16220 KB	Output is correct
11	Correct	5 ms	16220 KB	Output is correct
12	Correct	5 ms	16220 KB	Output is correct
13	Correct	6 ms	16220 KB	Output is correct
14	Correct	5 ms	16312 KB	Output is correct
15	Correct	5 ms	16216 KB	Output is correct
16	Correct	5 ms	16220 KB	Output is correct
17	Correct	5 ms	16220 KB	Output is correct
18	Correct	6 ms	16220 KB	Output is correct
19	Correct	5 ms	16220 KB	Output is correct
20	Correct	5 ms	16220 KB	Output is correct
21	Correct	5 ms	16220 KB	Output is correct
22	Correct	5 ms	16220 KB	Output is correct
23	Correct	5 ms	16220 KB	Output is correct
24	Correct	5 ms	16220 KB	Output is correct
25	Correct	5 ms	16220 KB	Output is correct
26	Correct	7 ms	16220 KB	Output is correct
27	Correct	6 ms	16220 KB	Output is correct
28	Correct	5 ms	16220 KB	Output is correct
29	Incorrect	6 ms	16216 KB	Output isn't correct
30	Halted	0 ms	0 KB	-