Submission #1170384

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170384		rayan_bd	Dreaming (IOI13_dreaming)	C++20	In queue	0 ms	0 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"

using namespace std;

#define ll long long
#define show(n) cout<<n<<'\n'
#define all(v) v.begin(), v.end()
#define pb push_back
#define fi first
#define se second

const int INF = 2e9;
const int mxN = 1e5 + 5000;

vector<pair<int,int>> adj[mxN];
bool vis[mxN];
int tot=0;

void dfs(int u,int par,int w,int &c){
	c=min(c,max(w,tot-w));
	vis[u]=1;
	for(auto it:adj[u]){
		if(it.fi^par){
			dfs(it.fi,u,w+it.se,c);
		}
	}
}

void calc_tot(int u,int par){
	for(auto it:adj[u]){
		if(it.fi^par){
			tot+=it.se;
			calc_tot(it.fi,u);
		}
	}
}

int travelTime(int N,int M,int L,int A[],int B[],int T[]){
	for(int i=0;i<N+5;++i){
		adj[i].clear();
		vis[i]=0;
		tot=0;
	}
	for(int i=0;i<M;++i) adj[A[i]].pb({B[i],T[i]}),adj[B[i]].pb({A[i],T[i]});
	int done=0,ans=L;
	for(int i=0;i<N&&done<2;++i){
		if(!vis[i]&&adj[i].size()<=1){
			tot=0;
			calc_tot(i,-1);
			int current=INF;
			dfs(i,-1,0,current);
			ans+=current;
			++done;
		}
	}
	return ans;
}