Submission #949936

#	Time	Username	Problem	Language	Result	Execution time	Memory
949936		Saul0906	Hotspot (NOI17_hotspot)	C++14	38 / 100	371 ms	16476 KiB

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;
		if(k>20)solve(u,v);
		else{
			int dis[n], dis2[n];
			bool vis[n]{}, vis2[n]{};
			queue<int> q;
			q.push(u);
			q.push(0);
			vis[u]=true;
			while(q.size()){
				int x=q.front(), w;
				q.pop();
				w=q.front();
				q.pop();
				dis[x]=w;
				repa(y,ady[x]){
					if(!vis[y]){
						vis[y]=true;
						q.push(y);
						q.push(w+1);
						vis[y]=true;
					}
				}
			}
			rep(j,0,n){
				fill(vis2,vis2+n,0);
				q.push(j);
				q.push(0);
				vis2[j]=true;
				while(q.size()){
					int x=q.front(), w;
					q.pop();
					w=q.front();
					q.pop();
					dis2[x]=w;
					repa(y,ady[x]){
						if(!vis2[y]){
							vis[y]=true;
							q.push(y);
							q.push(w+1);
							vis2[y]=true;
						}
					}
				}
				if(dis[v]==dis2[v]+dis[j] && dis[j]<=dis[v]) cont[j]++;
			}
		}
	}
	u=0;
	rep(i,0,lim) if(cont[u]<cont[i]) u=i;
	cout<<u<<endl;
}

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 11 / 11
• Subtask 4: 18 / 18
• Subtask 5: 0 / 26
• Subtask 6: 0 / 36