oj.uz

Submission #949932

# Submission time Handle Problem Language Result Execution time Memory
949932 2024-03-19T23:14:15 Z Saul0906 Hotspot (NOI17_hotspot) C++14
38 / 100
 7 ms 16312 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -