Submission #110173

#	Time	Username	Problem	Language	Result	Execution time	Memory
110173		ioilolcom	Dreaming (IOI13_dreaming)	C++14	0 / 100	58 ms	13176 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
#define s second
#define f  first
#define ll long long int
#define pb push_back
using namespace std;
 
const int N=1e5+7;
vector<pair<int,int> > adj[N];
bool vis[N];
int d[N];
int par[N];
int c[N];
int mx;
int start=-1,tok=-1;
void dfs(int u,int p,int l){
	vis[u]=1;
	for(auto v:adj[u]) {
		if(v.f==p) {
			continue;
		}
		dfs(v.f,u,l+v.s);
	}
	if(l>mx) {
		mx=l;
		start=u;
	}
}
void dfs2(int u,int p,int l){
	vis[u]=1;
	for(auto v:adj[u]) {
		if(v.f==p) {
			continue;
		}
		par[v.f]=u;
		d[v.f]=d[u]+v.s;
		dfs2(v.f,u,l+v.s);
	}
	if(l>mx) {
		mx=l;
		tok=u;
	}
}
int radius(int u,int p){
	//memset(par,-1,sizeof par);
	mx=0;
	start=-1; tok=-1;
	dfs(u,p,0);
	mx=0;
	if(start==-1) {
		return 0;
	}
	dfs2(start,p,0);
	int diameter=mx;
	int ans=1e9;
 
	for(int u=tok; u!=start; u=par[u]) {
		//cout<<u<<" "<<d[u]<<endl;
		ans=min(ans,max(diameter-d[u],d[u]));
	}
//	cout<<ans<<endl;
	return ans;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	int n=N;
	int m=M;
	int l=L;
	for(int i=0; i<M; i++) {
		int u=A[i];
		int v=B[i];
		int w=T[i];
		adj[u].pb({v,w});
		adj[v].pb({u,w});
	}
	int cnt=1;
	for(int i=0; i<n; i++) {
		if(!vis[i]) {
			vis[i]=1;
			//dfs(i,-1,0);
			c[cnt]=radius(i,-1);
			cnt++;
		}
	}


	int mx1=0;
	int mx2=0;
	for(int i=1; i<cnt; i++) {
		if(c[i]>mx1) {
			mx2=mx1;
			mx1=c[i];
		}
		else if(c[i]>mx2) {
			mx2=c[i];
		}
	}
	int lol=mx1;
	if(cnt>2) {
		lol+=(mx2+l);
	}
//	cout<<cnt<<endl;
	//cout<<lol<<endl;
	return lol;
}

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:67:6: warning: unused variable 'm' [-Wunused-variable]
  int m=M;
      ^

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