Submission #383544

#	Time	Username	Problem	Language	Result	Execution time	Memory
383544		Keshi	Dreaming (IOI13_dreaming)	C++17	100 / 100	151 ms	20332 KiB

dreaming

//In the name of God
#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;

typedef int ll;
typedef pair<ll, ll> pll;

const ll maxn = 2e5 + 100;
const ll mod = 1e9 + 7;
const ll inf = 1e9;

#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout);
#define pb push_back
#define Mp make_pair
#define F first
#define S second
#define Sz(x) ll((x).size())
#define all(x) (x).begin(), (x).end()

ll d[2][maxn];
vector<pll> g[maxn];
bool vis1[maxn], vis[maxn];
vector<ll> vec;

void dfs1(ll v){
	vec.pb(v);
	vis1[v] = 1;
	for(pll u : g[v]){
		if(!vis1[u.F]) dfs1(u.F);
	}
	return;
}

void dfs(ll v, ll t){
	vis[v] = 1;
	for(pll u : g[v]){
		if(!vis[u.F]){
			d[t][u.F] = d[t][v] + u.S;
			dfs(u.F, t);
		}
	}
	return;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	for(ll i = 0; i < M; i++){
		g[A[i]].pb(Mp(B[i], T[i]));
		g[B[i]].pb(Mp(A[i], T[i]));
	}
	ll mx = 0;
	vector<ll> a;
    for(ll i = 0; i < N; i++){
		if(vis1[i]) continue;
		vec.clear();
		dfs1(i);
		d[0][i] = 0;
		dfs(i, 0);
		ll v = vec[0];
		for(ll u : vec){
			vis[u] = 0;
			if(d[0][u] > d[0][v]) v = u;
		}
		d[1][v] = 0;
		dfs(v, 1);
		ll x = vec[0];
		for(ll u : vec){
			vis[u] = 0;
			if(d[1][u] > d[1][x]) x = u;
		}
		d[0][x] = 0;
		dfs(x, 0);
		ll r = inf;
		for(ll u : vec){
			vis[u] = 0;
			ll dd = max(d[0][u], d[1][u]);
			mx = max(mx, dd);
			r = min(r, dd);
		}
		a.pb(r);
	}
	sort(all(a), greater<ll>());
	if(Sz(a) > 1) mx = max(mx, a[0] + a[1] + L);
	if(Sz(a) > 2) mx = max(mx, a[2] + a[1] + L + L);
	return mx;
}

/*int main(){
    fast_io;

	int n, m, l, a[100], b[100], c[100];
	cin >> n >> m >> l;
	for(ll i = 0; i < m; i++){
		cin >> a[i] >> b[i] >> c[i];
	}
	cout << travelTime(n, m, l, a, b, c);

    return 0;
}*/

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