Submission #906249

#	Time	Username	Problem	Language	Result	Execution time	Memory
906249		Mathias	Dreaming (IOI13_dreaming)	C++14	100 / 100	66 ms	20308 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
const int INF = 1<<31-1;
const int MAXN = 1e5+7;
int xd[MAXN][3];
int ojc[MAXN];
int sum[MAXN];
bool visited[MAXN][3];
vector<int> v;
vector<pair<int,int> > g[MAXN];
int a,b,c,d,m,w,d1,curr,r;
void DFS1(int x,int f,int k){
	visited[x][k]=1;
	for(auto s:g[x]){
		if(s.first==f) continue;
		xd[s.first][k]=max(xd[s.first][k], xd[x][k]+s.second);
		if(xd[s.first][k]>m){
			m=xd[s.first][k];
			d=s.first;
		}
		DFS1(s.first,x,k);
	}
}
void DFS2(int x,int f,int k){
	visited[x][k]=1;
	ojc[x]=f;
	for(auto s:g[x]){
		if(s.first==f) continue;
		xd[s.first][k]=max(xd[s.first][k], xd[x][k]+s.second);
		sum[s.first]=sum[x]+s.second;
		if(xd[s.first][k]>m){
			m=xd[s.first][k];
			d1=s.first;
		}
		DFS2(s.first,x,k);
	}
}
int p=0;
int travelTime(int N,int M,int L,int A[],int B[],int T[]){
	for(int i=0;i<M;i++){
		g[A[i]].push_back({B[i], T[i]});
		g[B[i]].push_back({A[i], T[i]});
	}
	for(int i=0;i<N;i++){
		if(visited[i][0]==0){
			m=0; d=i , d1=i;
			DFS1(i,MAXN-1,0);
			m=0;
			DFS2(d,MAXN-1,1);
			r=INF;
			curr=d1;
			p=max(p,sum[curr]);
			while(curr!=MAXN-1){
				if(max(sum[d1]-sum[curr], sum[curr])<r){
					r=max(sum[d1]-sum[curr], sum[curr]);
					w=curr;
				}
				curr=ojc[curr];
			}
			v.push_back(r);
		}
	}
	if(v.size()==1){
		return p;
	}
	else if(v.size()==2){
		a=v[0];
		b=v[1];
		//cout<<a<<' '<<b<<' '<<L<<'\n';
		return max(a+b+L,p);
	}
	else{
		sort(v.begin(),v.end());
		reverse(v.begin(), v.end());
		a=v[0];
		b=v[1];
		c=v[2];	
		//cout<<a<<' '<<b<<' '<<c<<'\n';
		return max({a+b+L,b+c+2*L,p});
	}
}/*
int main(){
	int A[100], B[100], T[100];
	int n,m,l;
	cin>>n>>m>>l;
	for(int i=0;i<m;i++) cin>>A[i]>>B[i]>>T[i];
	cout<<travelTime(n,m,l,A,B,T)<<'\n';
}
*/

Compilation message (stderr)

dreaming.cpp:4:22: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
    4 | const int INF = 1<<31-1;
      |                    ~~^~

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