Submission #1318214

#	Time	Username	Problem	Language	Result	Execution time	Memory
1318214		Johan	꿈 (IOI13_dreaming)	C++20	0 / 100	459 ms	32824 KiB

dreaming

#include "dreaming.h"
#include "bits/stdc++.h"
using namespace std;
const int N = 1e5 + 5;
int pa[N];
vector < int > adj[N];
map < int , int > dist;
map < pair < int , int > , int > we;
vector < int > par(N, -1);
int find(int u){
	if(par[u] < 0)return u;
	else return par[u] = find(par[u]);
}
void uni(int u, int v){
	u = find(u);
	v = find(v);
	if(u == v)return;
	par[u] += par[v];
	par[v] = u;
}
void dfs(int u, int p = -1){
	for(auto v : adj[u]){
		if(v != p){
			dist[v] = dist[u] + we[{u, v}];
			dfs(v, u);
		}
	}
}
void dfs_(int u, int end, int p = -1){
	pa[u] = p;
	for(auto v : adj[u]){
		if(v != p)
			dfs_(v, end, u);
	}
}
array < int , 3 > centre(int st, int end){
	int sz = 0;
	vector < int > path = {end};
	while(end != st){
		sz += we[{end, pa[end]}];
		end = pa[end];
		path.push_back(end);		
	}
	int mn = sz, diametr = sz, cur = 0, node = path[0], far;
	for(int i = 1; i < path.size(); i++){
		int W = we[{path[i], path[i - 1]}];
		sz -= W;
		cur += W;
		if(mn > max(sz, cur)){
			if(sz > cur)far = path.back();
			else far = path[0];
			mn = max(sz, cur);
			node = path[i];
		}
	}
	return {diametr, node, mn};
}
int travelTime(int n, int m, int L, int u[], int v[], int w[]){
	for(int i = 0; i < m; i++){
		we[{u[i], v[i]}] = w[i];
		we[{v[i], u[i]}] = w[i];
		adj[u[i]].push_back(v[i]);
		adj[v[i]].push_back(u[i]);	
		uni(u[i], v[i]);
	}
	set < int > cmps;
	for(int i = 0; i < n; i++)
		cmps.insert(find(i));
	vector < array < int , 3 > > x;
	for(auto nd : cmps){
		dfs(nd);
		int mx = 0, u = nd, v = nd;
		for(auto e : dist){
			int node = e.first;
			int dis = e.second;
			if(dis > mx){
				mx = dis;
				u = node;
			}
		}
		mx = 0;
		dist.clear();
		dfs(u);
		for(auto e : dist){
			int node = e.first;
			int dis = e.second;
			if(dis > mx){
				mx = dis;
				v = node;
			}
		}
		dist.clear();
		dfs_(u, v);
		x.push_back(centre(u, v));
	}
	sort(x.rbegin(), x.rend());
	int Node = x[0][1], diss = x[0][2];
	for(int i = 1; i < x.size(); i++){
		adj[Node].push_back(x[i][1]);
		adj[x[i][1]].push_back(Node);
		we[{Node, x[i][1]}] = L;
		we[{x[i][1], Node}] = L;
		int mx = max(x[0][0], x[i][0]);
		if(mx < L + diss + x[i][2]){
			diss = max(diss, L + x[i][2] + 2);
			mx = 	L + diss + x[i][2];
		}
		x[0][0] = mx;
	}
	return x[0][0];
}
/*
12 8 2
0 8 4
8 2 2
2 7 4
5 11 3
5 1 7
1 3 1
1 9 5
10 6 3
*/

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