Submission #1169764

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169764		jadai007	Dreaming (IOI13_dreaming)	C++20	18 / 100	33 ms	9292 KiB

dreaming

/*
    Author : detective conan
    Problem : IOI13_dreaming
    Created : 14:14 UTC+7
*/
#include <bits/stdc++.h>
#include "dreaming.h"
#define FOR(i, s, t) for(int i = s; i <= t; ++i)
#define rep(i, s, t) for(int i = s; i >= t; --i)
#define HAVE_TESTCASE false
#define conan cin.tie(nullptr)->sync_with_stdio(false)
#define mod (int)(1e9 + 7)
#define vec vector
#define pii pair<int, int>
#define ari(n) array<int, n>
#define pb push_back
#define eb emplace_back
#define ph push
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define ANS(n, s) cout << n << s

using namespace std;
using u32 = unsigned;
using i64 = int64_t;
using u64 = unsigned i64;

const int MAX_N = 1e5 + 10;
vec<pii> vc[MAX_N];
int dp[MAX_N][3], vis[MAX_N][3];
vec<int> dis;

int findmax(int u){
    int mx = -1, root = 0, leaf = 0;
    vec<int> all;
    queue<pii> q;
    q.emplace(u, 0);
    dp[u][0] = 0;
    while(!q.empty()){
        int u = q.front().first, cnt = q.front().second;
        q.pop();
        if(vis[u][0]) continue;
        all.pb(u);
        vis[u][0] = 1;
        dp[u][0] = cnt;
        if(mx < dp[u][0]) mx = dp[u][0], root = u;
        for(auto x:vc[u]){
            int v = x.first, w = x.second;
            if(!vis[v][0]) q.emplace(v, cnt + w);
        }
    }
    mx = -1;
    q.emplace(root, 0);
    dp[root][1] = 0;
    while(!q.empty()){
        int u = q.front().first, cnt = q.front().second;
        q.pop();
        if(vis[u][1]) continue;
        vis[u][1] = 1;
        dp[u][1] = cnt;
        if(mx < dp[u][1]) mx = dp[u][1], leaf = u;
        for(auto x:vc[u]){
            int v = x.first, w = x.second;
            if(!vis[v][1]) q.emplace(v, cnt + w);
        }
    }
    q.emplace(leaf, 0);
    dp[leaf][2] = 0;
    while(!q.empty()){
        int u = q.front().first, cnt = q.front().second;
        q.pop();
        if(vis[u][2]) continue;
        vis[u][2] = 1;
        dp[u][2] = cnt;
        for(auto x:vc[u]){
            int v = x.first, w = x.second;
            if(!vis[v][2]) q.emplace(v, w + cnt);
        }
    }
    mx = 1e9;
    for(auto u:all) mx = min(mx, max(dp[u][1], dp[u][2]));
    return mx;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]){
    FOR(i, 0, M - 1) vc[A[i]].eb(B[i], T[i]), vc[B[i]].eb(A[i], T[i]);
    FOR(i, 0, N - 1) if(!vis[i][0]) dis.pb(findmax(i));
    sort(dis.begin(), dis.end(), greater<int>());
    if(dis.size() == 1) return dis[2];
    else if(dis.size() == 2) return dis[0] + dis[1] + L;
    else return max(dis[0] + dis[1] + L, dis[1] + dis[2] + 2*L);
}
/*
int32_t main() {
    conan;
	int N, M, L, i;
	int res;

	cin >> N >> M >> L;
	for (i = 0; i < M; i++) cin >> A[i] >> B[i] >> T[i];
	int answer = travelTime(N, M, L, A, B, T);
	cout << answer;

	return 0;
}
    */

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