oj.uz

Submission #110173

# Submission time Handle Problem Language Result Execution time Memory
110173 2019-05-09T18:14:51 Z ioilolcom Dreaming (IOI13_dreaming) C++14
0 / 100
 58 ms 13176 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 58 ms 13176 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 58 ms 13176 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 58 ms 13176 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 6144 KB Output is correct
2 Incorrect 25 ms 6136 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 58 ms 13176 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 58 ms 13176 KB Output isn't correct
2 Halted 0 ms 0 KB -