Submission #297855

#	Time	Username	Problem	Language	Result	Execution time	Memory
297855		Bill_00	Dreaming (IOI13_dreaming)	C++14	32 / 100	88 ms	15352 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
using namespace std;
vector<long long>vec;
long long vis[100001],id,p=0,path,res=0;
long long cost[100001];
int go[100001];
vector<pair<int,long long> >adj[100001];
void dfsd(int u,int v,long long w){
	cost[u]=w;
	if(w>path){
		id=u;
		path=w;
	}
	go[u]=v;
	for(int i=0;i<adj[u].size();i++){
		int f=adj[u][i].ff;
		long long s=adj[u][i].ss;
		if(f!=v){
			dfsd(f,u,w+s);
		}
	}
	
}
void dfs(int u,int v,int w){
	vis[u]=1;
	if(w>p){
		id=u;
		p=w;
	}
	for(int i=0;i<adj[u].size();i++){
		int f=adj[u][i].ff;
		long long s=adj[u][i].ss;
		if(f!=v){
			dfs(f,u,w+s);
		}
	}
}
int travelTime(int n, int m, int L, int a[], int b[], int t[]){
	for(int i=0;i<m;i++){
		adj[a[i]].pb(mp(b[i],(long long)t[i]));
		adj[b[i]].pb(mp(a[i],(long long)t[i]));
	}
    for(int i=0;i<n;i++){
    	if(!vis[i]){
    		path=0;
    		p=0;
    		id=0;
    		dfs(i,-1,0);
    		dfsd(id,-1,0);
    		res=max(res,path);
    		long long ans=1e18;
    		while(id!=-1){
    			ans=min(ans,max(path-cost[id],cost[id]));
    			id=go[id];
			}
			vec.pb(ans);
		}
	}
	sort(vec.begin(),vec.end());
	if(vec.size()>=2) res=max(res,vec[vec.size()-1]+vec[vec.size()-2]+L);
	if(vec.size()>2) res=max(res,vec[vec.size()-2]+vec[vec.size()-3]+2*L);
	return res;
}

Compilation message (stderr)

dreaming.cpp: In function 'void dfsd(int, int, long long int)':
dreaming.cpp:20:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |  for(int i=0;i<adj[u].size();i++){
      |              ~^~~~~~~~~~~~~~
dreaming.cpp: In function 'void dfs(int, int, int)':
dreaming.cpp:35:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |  for(int i=0;i<adj[u].size();i++){
      |              ~^~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 0 / 10
• Subtask 3: 0 / 23
• Subtask 4: 18 / 18
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23