제출 #1170387

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1170387		rayan_bd	꿈 (IOI13_dreaming)	C++20	14 / 100	31 ms	15428 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;
	}
	int t[3];
	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;
			t[done]=tot;
			++done;
		}
	}
	ans=max({ans,t[0],t[1]});
	return ans;
}

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