Submission #1058948

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058948		MrDogMeat	Dreaming (IOI13_dreaming)	C++17	100 / 100	38 ms	17112 KiB

dreaming

#include<bits/stdc++.h>
#include "dreaming.h"

using namespace std;

#define FI first
#define SE second

const int MAX_N = 1e5 + 5;

///graph traverse
vector<pair<int, int>> adj[MAX_N];

///cal min longest path for each tree
bool use[MAX_N];
pair<int, int> f[MAX_N];
int Min;

///cal ans
vector<int> vec;
int Ans;

void maximize_pair(pair<int,int> &a, int v) {
    if(v > a.FI) {
        a.SE = a.FI;
        a.FI = v;
    }
    else if(v > a.SE) {
        a.SE = v;
    }
}

void dfs1(int u, int par) {
    use[u] = 1;
    for(auto v : adj[u]) if(v.FI != par) {
        dfs1(v.FI, u);
        maximize_pair(f[u], f[v.FI].FI + v.SE);
    }
}

void reroot(int u, int par) {
    Min = min(Min, f[u].FI);
    Ans = max(Ans, f[u].FI + f[u].SE);
    for(auto v : adj[u]) if(v.FI != par) {
        if(f[v.FI].FI + v.SE == f[u].FI) {
            maximize_pair(f[v.FI], f[u].SE + v.SE);
        }
        else {
            maximize_pair(f[v.FI], f[u].FI + v.SE);
        }
        reroot(v.FI, u);
    }
}

void cal(int u) {
    dfs1(u, 0);
    Min = INT_MAX;
    reroot(u, 0);
    vec.push_back(Min);
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    for(int i = 0; i < M; i++) {
        adj[A[i]].emplace_back(B[i], T[i]);
        adj[B[i]].emplace_back(A[i], T[i]);
    }

    Ans = 0;
    for(int u = 0; u < N; u++) if(!use[u]) {
        cal(u);
    }

    if(vec.size() == 2) {
        Ans = max(Ans, vec[0] + vec[1] + L);
    }
    else if(vec.size() > 2) {
        sort(vec.begin(), vec.end());
        reverse(vec.begin(), vec.end());
        Ans = max(Ans, max(vec[0] + vec[1] + L, vec[1] + vec[2] + 2 * L));
    }

    return 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