Submission #676938

#	Time	Username	Problem	Language	Result	Execution time	Memory
676938		penguin133	Dreaming (IOI13_dreaming)	C++17	100 / 100	76 ms	20032 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){
  vis[x] = 1;
	if(cur > maxi)maxi = cur, pos = x;
	for(auto [i, j] : v[x])if(i != p)diam(i, x, cur + j);
}
 
vector<pi> mids; vector<int> 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;
vector<pi>dist;
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[]) {
	int ans = 0;
	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);
          ans = max(ans, maxi);
			//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, mn});
			dist.push_back({mn, cent});
		}
	}
	//for(auto i : mids)cerr << i << " ";
	//cerr << '\n';
	sort(dist.begin(), dist.end(), greater<pi>());
	ll mini = INT_MAX;
	for(auto [i, j] : mids){
		pi pos = {-1, -1}, pos2 = {-1, -1};
		for(int k=0;k<(int)dist.size();k++){
			if(dist[k].se == i)continue;
			if(pos.fi == -1)pos = dist[k];
			else {
				pos2 = dist[k];
				break;
			}
		}
		if(pos.fi == -1)mini = min(mini, j);
		else if(pos2.fi == -1)mini = min(mini, j + L + pos.fi);
		else mini = min(mini, max(j + L + pos.fi, 2 * L + pos.fi + pos2.fi));
	}
	return max(mini, ans);
}

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