Submission #253211

#	Time	Username	Problem	Language	Result	Execution time	Memory
253211		nandonathaniel	Hotspot (NOI17_hotspot)	C++14	100 / 100	1426 ms	154944 KiB

hotspot

#include<bits/stdc++.h>
using namespace std;
const int INF=1e9;
vector<int> adj[5005];
int dist[5005][5005],cara[5005][5005],ret[5005];
double byk[5005];
bool flag[5005];
int a[2005],b[2005];

int main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N,M,u,v,K;
    cin >> N >> M;
    for(int i=1;i<=M;i++){
    	cin >> u >> v;
    	adj[u].push_back(v);
    	adj[v].push_back(u);
	}
	for(int i=0;i<N;i++){
		memset(flag,false,sizeof(flag));
		for(int j=0;j<N;j++){
			dist[i][j]=INF;
		}
		cara[i][i]=1;
		dist[i][i]=0;
		queue<int> Q;
		Q.push(i);
		while(!Q.empty()){
			int s=Q.front();
			Q.pop();
			for(int j=0;j<adj[s].size();j++){
				int t=adj[s][j];
				if(!flag[t]){
					if(dist[i][t]>dist[i][s]+1){
						dist[i][t]=dist[i][s]+1;
						cara[i][t]+=cara[i][s];
						flag[t]=true;
						Q.push(t);
					}
				}
				else{
					if(dist[i][s]+1==dist[i][t]){
						cara[i][t]+=cara[i][s];
					}
				}
			}
		}
	}
	cin >> K;
	for(int i=1;i<=K;i++){
		cin >> a[i] >> b[i];
		memset(ret,0,sizeof(ret));
		for(int j=0;j<N;j++){
			if(dist[a[i]][j]+dist[j][b[i]]==dist[a[i]][b[i]]){
				ret[j]=(cara[a[i]][j]*cara[j][b[i]]);
				byk[j]+=(double)ret[j]/cara[a[i]][b[i]];
			}
		}
	}
	double maxi=-1.0;
	int ans;
	for(int i=0;i<N;i++){
		if(byk[i]>maxi){
			maxi=byk[i];
			ans=i;
		}
	}
	cout << ans << endl;
	return 0;
}

Compilation message (stderr)

hotspot.cpp: In function 'int main()':
hotspot.cpp:33:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0;j<adj[s].size();j++){
                ~^~~~~~~~~~~~~~
hotspot.cpp:70:10: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
  cout << ans << endl;
          ^~~

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