Submission #738134

#TimeUsernameProblemLanguageResultExecution timeMemory
738134mosiashvililukaHotspot (NOI17_hotspot)C++14
100 / 100
828 ms1284 KiB
#include<bits/stdc++.h> using namespace std; long double A,B,C,D,X,Y,Z,val[5009],pas; int a,b,c,d,e,i,j,ii,jj,zx,xc,tes,t,dp[5009][2],bo[5009],lvl[5009],dis[5009][2],ans; vector <int> v[5009]; deque <int> de; void fun(int q, int w, int H){ while(de.size()) de.pop_back(); for(i=0; i<=a+2; i++){ dp[i][H]=0;bo[i]=0;lvl[i]=0;dis[i][H]=a+4; } dp[q][H]=1;lvl[q]=1;bo[q]=1;dis[q][H]=0; de.push_back(q); while(de.size()){ c=de.front();de.pop_front(); for(vector <int>::iterator it=v[c].begin(); it!=v[c].end(); it++){ if(bo[(*it)]==1){ if(lvl[(*it)]==lvl[c]+1){ dp[(*it)][H]+=dp[c][H]; } continue; } dis[(*it)][H]=dis[c][H]+1; lvl[(*it)]=lvl[c]+1; dp[(*it)][H]=dp[c][H]; bo[(*it)]=1; de.push_back((*it)); } } } int main(){ ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0); cin>>a>>b; for(i=1; i<=b; i++){ cin>>c>>d;c++;d++; v[c].push_back(d); v[d].push_back(c); } cin>>tes; for(t=1; t<=tes; t++){ cin>>c>>d;c++;d++; fun(c,d,0); fun(d,c,1); for(i=1; i<=a; i++){ if(dis[i][0]+dis[i][1]!=dis[d][0]) continue; A=dp[d][0]; B=dp[i][0];C=dp[i][1];B*=C; val[i]+=B/A; } } pas=-1.0;ans=0; for(i=1; i<=a; i++){ if(val[i]>pas){ pas=val[i];ans=i; } } //cout<<setprecision(12)<<pas<<"\n"; cout<<ans-1; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...