Submission #1174125

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174125		StefanSebez	Dreaming (IOI13_dreaming)	C++20	65 / 100	232 ms	25064 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=1e5+50;
int n,m,L;
vector<pair<int,int>>E[N];
map<pair<int,int>,int>edge;
int maksdepth,makscvor,par[N];
int komp[N],cnt;
void DFS(int u,int parent,int depth){
	par[u]=parent;
	if(maksdepth<=depth) makscvor=u;
	maksdepth=max(maksdepth,depth);
	komp[u]=cnt;
	for(auto [i,x]:E[u]){
		if(i==parent) continue;
		DFS(i,u,depth+x);
	}
}
int travelTime(int n1, int m1, int L1, int A[], int B[], int T[]) {
    n=n1,m=m1,L=L1;
    for(int i=0;i<m;i++){
		E[A[i]].pb({B[i],T[i]});
		E[B[i]].pb({A[i],T[i]});
		edge[{A[i],B[i]}]=edge[{B[i],A[i]}]=T[i];
    }
    vector<pair<int,int>>a;
    for(int i=0;i<n;i++){
		//printf("%i\n",i);
		if(komp[i]) continue;
		cnt++;
		maksdepth=makscvor=-1;
		DFS(i,-1,0);
		int u=makscvor;
		maksdepth=makscvor=-1;
		DFS(u,-1,0);
		int v=makscvor,d=maksdepth,d1=0;
		int val=1e9;
		while(v!=-1){
			val=min(val,max(d,d1));
			int x=edge[{v,par[v]}];
			d-=x,d1+=x;
			v=par[v];
		}
		a.pb({maksdepth,val});
    }
    //for(int i=0;i<n;i++) printf("%i: %i\n",i,komp[i]);
    //for(auto [u,v]:a) printf("%i %i\n",u,v);
    sort(a.begin(),a.end());
    for(int i=0;i+1<a.size();i++){
		pair<int,int>x=a[i],y=a.back();
		if(x.se+y.se+L>y.fi){
			a.back().fi=x.se+y.se+L;
			a.back().se=min(max(x.se+L,y.se),max(x.se,y.se+L));
		}
    }
    return a.back().fi;
}

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