Submission #676935

#	Time	Username	Problem	Language	Result	Execution time	Memory
676935		penguin133	Dreaming (IOI13_dreaming)	C++17	0 / 100	1098 ms	65536 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
 
//#define int long long
typedef int ll;
#define pi pair<int, ll>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
 
int vis[100005];
vector<pi>v[100005], adj[100005];
ll maxi = -1e9, pos;
vector<int> trav;
void dfs(int x, ll cur){
	if(vis[x])return;
	vis[x] = 1;
	trav.push_back(x);
	if(cur > maxi)maxi = cur, pos = x;
	for(auto [i, j] : v[x])dfs(i, cur + j);
}
 
void diam(int x, int p, ll cur){
	if(cur > maxi)maxi = cur, pos = x;
	for(auto [i, j] : v[x])if(i != p)diam(i, x, cur + j);
}
 
vector<int> mids, path;
 
void find(int cur, int tgt, int p){
	trav.push_back(cur);
	if(cur == tgt){
		path = trav;
		return;
	}
	for(auto [i, j] : v[cur])if(i != p)find(i, tgt, cur);
	trav.pop_back();
}
 
ll mx;
 
void recur(int x, int p, ll cur){
	mx = max(mx, cur);
	for(auto [i, j] : v[x])if(i != p)recur(i, x, cur + j);
}
 
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	
	for(int i=0;i<M;i++)v[A[i]].push_back({B[i], T[i]}), v[B[i]].push_back({A[i], T[i]});
	for(int i=0;i<N;i++){
		if(!vis[i]){
			maxi = -1e9;
			diam(i, -1, 0);
			int pos2 = pos;
			maxi = -1e9;
			diam(pos, -1, 0);
			//cerr << pos << " " << pos2 << '\n';
			ll cur = 0;
			ll mn = INT_MAX; 
			find(pos2, pos, -1);
			int cent = path[0];
			trav.clear();
			for(int j=0;j<(int)path.size();j++){
				mx = max(cur, maxi - cur);
				for(auto [a, b] : v[path[j]]){
					if((!j || path[j-1] != a) && (j == (int)path.size() - 1 || path[j+1] != a))recur(a, path[j], b);
					if(j < (int)path.size() - 1 && a == path[j+1])cur += b;
				}
				if(mn > mx)mn = mx, cent = path[j];
			}
			//cerr << cent << '\n';
			mids.push_back(cent);
		}
	}
	//for(auto i : mids)cerr << i << " ";
	//cerr << '\n';
	ll mini = INT_MAX;
	for(int i=0;i<(int)mids.size();i++){
		for(int j=0;j<(int)mids.size();j++){
			if(j == i)continue;
			v[mids[i]].push_back({mids[j], L});
			v[mids[j]].push_back({mids[i], L});		
		}
		maxi = -1e9;
		diam(0, -1, 0);
		maxi = -1e9;
		diam(pos, -1, 0);
		//cerr << maxi << '\n';
		mini = min(mini, maxi);
		for(int j=0;j<(int)mids.size();j++){
			if(j == i)continue;
			v[mids[j]].pop_back();
		}
		for(int j=0;j<(int)mids.size()-1;j++)v[mids[i]].pop_back();
	}
	return mini;
}

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