Submission #1194223

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194223		PlayVoltz	Dreaming (IOI13_dreaming)	C++20	100 / 100	97 ms	20292 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pii pair<int, int>
#define mp make_pair
#define pb push_back

int n, m, l, counter=0;
vector<vector<pii> > graph;
vector<vector<int> > comp;
vector<int> dist, dsu, in, out;
vector<bool> visited;

int fp(int node){
	if (dsu[node]==node)return node;
	return dsu[node]=fp(dsu[node]);
}

void merge(int a, int b){
	int pa=fp(a), pb=fp(b);
	dsu[pa]=pb;
}

void dfs(int node, int par, int d){
	visited[node]=1;
	in[node]=++counter;
	dist[node]=d;
	for (auto num:graph[node])if (num.first!=par)dfs(num.first, node, d+num.second);
	out[node]=counter;
}

bool ispar(int a, int b){
	return in[a]<=in[b] && out[a]>=in[b];
}

pii dialen(int node){
	pii res;
	dfs(node, -1, 0);
	int mx=-1, dia1, dia2;
	for (auto i:comp[fp(node)]){
		if (dist[i]>mx){
			mx=dist[i];
			dia1=i;
		}
	}
	dfs(dia1, -1, 0);
	res.first=-1;
	for (auto i:comp[fp(dia1)]){
		if (dist[i]>res.first){
			res.first=dist[i];
			dia2=i;
		}
	}
	res.second=LLONG_MAX;
	queue<int> q;
	q.push(dia1);
	int trav=0, left=res.first;
	while (!q.empty()){
		int cnode=q.front();
		q.pop();
		res.second=min(res.second, max(trav, left));
		for (auto num:graph[cnode]){
			if (ispar(cnode, num.first)&&ispar(num.first, dia2)){
				q.push(num.first);
				trav+=num.second;
				left-=num.second;
			}
		}
	}
	return res;
}

signed travelTime(signed N, signed M, signed L, signed A[], signed B[], signed T[]){
	n=N, m=M, l=L;
	graph.resize(n);
	visited.resize(n, 0);
	dsu.resize(n, -1);
	in.resize(n);
	out.resize(n);
	dist.resize(n);
	comp.resize(n);
	for (int i=0; i<n; ++i)dsu[i]=i;
	for (int i=0; i<m; ++i){
		graph[A[i]].pb(mp(B[i], T[i]));
		graph[B[i]].pb(mp(A[i], T[i]));
		merge(A[i], B[i]);
	}
	for (int i=0; i<n; ++i)comp[fp(i)].pb(i);
	if (m==n-1)return dialen(0).first;
	vector<int> vals, dia;
	for (int i=0; i<n; ++i){
		if (!visited[i]){
			pii res = dialen(i);
			dia.pb(res.first);
			vals.pb(res.second);
		}
	}
	sort(dia.begin(), dia.end(), greater<int>());
	sort(vals.begin(), vals.end(), greater<int>());
	if (m==n-2)return max(dia[0], vals[0]+vals[1]+l);
	return max(dia[0], max(vals[0]+vals[1]+l, vals[1]+vals[2]+2*l));
}

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