Submission #1167233

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167233		InvMOD	Dreaming (IOI13_dreaming)	C++20	100 / 100	82 ms	26184 KiB

dreaming

#include<bits/stdc++.h>

//#define name "InvMOD"
#ifndef name
    #include "dreaming.h"
#endif // name

using namespace std;

#define sz(v) (int)(v).size()
#define all(v) (v).begin(), (v).end()
#define dbg(x) "[" << #x " = " << (x) << "]"

template<typename T> bool ckmx(T& a, const T& b){
    if(a < b)
        return a = b, true;
    return false;
}

int travelTime(int n, int m, int L, int A[], int B[], int T[]){
    vector<vector<int>> adj(n, vector<int>());

    for(int i = 0; i < m; i++){
        adj[A[i]].push_back(i);
        adj[B[i]].push_back(i);
    }

    vector<int> d(n, -1), Mx(n, 0);
    function<void(int,int)> preDFS = [&](int x, int p) -> void{
        d[x] = 0;
        for(int id : adj[x]){
            int v = A[id] ^ B[id] ^ x, w = T[id];
            if(v != p){
                preDFS(v, x);
                ckmx(d[x], d[v] + w);
            }
        }
        return;
    };

    function<int(int,int,int)> dp = [&](int x, int p, int dpar) -> int{
        vector<int> mxDist = {dpar};

        for(int id : adj[x]){
            int v = A[id] ^ B[id] ^ x;
            if(v != p) mxDist.push_back(d[v] + T[id]);
        }
        sort(all(mxDist), greater<int>());

        int answer = mxDist[0];
        for(int id : adj[x]){
            int v = A[id] ^ B[id] ^ x;
            if(v == p) continue;
            int nDist = (mxDist[0] == d[v] + T[id] ? mxDist[1] : mxDist[0]);
            answer = min(answer, dp(v, x, nDist + T[id]));
        }

        Mx[x] = mxDist[0] + (sz(mxDist) > 1 ? mxDist[1] : 0);
        return answer;
    };

    vector<int> dist;
    for(int i = 0; i < n; i++){
        if(d[i] == -1){
            preDFS(i, -1);
            dist.push_back(dp(i, -1, 0));
        }
    }
    sort(all(dist), greater<int>());

    int answer = 0;
    if(sz(dist) == 1){
        answer = dist[0];
    }
    else if(sz(dist) == 2){
        answer = dist[0] + L + dist[1];
    }
    else  answer = max(dist[0] + L + dist[1], dist[1] + 2 * L + dist[2]);

    answer = max(answer, *max_element(all(Mx)));
    return answer;
}

#ifdef name
    int32_t main(){
        freopen(name".INP", "r", stdin);
        freopen(name".OUT", "w", stdout);

        int n,m,L; cin >> n >> m >> L;

        int A[m], B[m], T[m];
        for(int i = 0; i < m; i++){
            cin >> A[i] >> B[i] >> T[i];
        }

        cout << travelTime(n, m, L, A, B, T) << "\n";
        return 0;
    }
#endif // name

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