Submission #1266878

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266878		junior0036	Dreaming (IOI13_dreaming)	C++20	100 / 100	83 ms	19132 KiB

dreaming

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

#define ll long long
#define endl "\n"
using namespace std;

vector<vector<pair<int, ll>>> adj;
vector<pair<ll, int>> dp1, dp2, path;
vector<int> pt, used;

void dfsf(int v, int e){
    used[v] = 1;
    pt.push_back(v);
    for(auto &u : adj[v]){
        if(u.first == e) continue;
        dfsf(u.first, v);
        ll val = dp1[u.first].first + u.second;
        if(val >= dp1[v].first){
            dp2[v] = dp1[v];
            dp1[v] = {val, u.first};
        } else if(val >= dp2[v].first){
            dp2[v] = {val, u.first};
        }
    }
}

void dfss(int v, int e){
    for(auto &u : adj[v]){
        if(u.first == e) continue;
        ll val;
        if(u.first == dp1[v].second) val = dp2[v].first + u.second;
        else val = dp1[v].first + u.second;

        if(val >= dp1[u.first].first){
            dp2[u.first] = dp1[u.first];
            dp1[u.first] = {val, v};
        } else if(val >= dp2[u.first].first){
            dp2[u.first] = {val, v};
        }

        dfss(u.first, v);
    }
}

void prepare(int pos){
    pt.clear();
    dfsf(pos, -1);
    dfss(pos, -1);

    ll mx = 0;
    for(int v : pt){
        mx = max(mx, dp1[v].first + dp2[v].first);
    }

    int idx = -1;
    ll mn = LLONG_MAX;
    for(int v : pt){
        ll val = dp1[v].first + dp2[v].first;
        if(val == mx){
            ll x = max(dp1[v].first, dp2[v].first);
            if(x < mn){
                mn = x;
                idx = v;
            }
        }
    }

    path.push_back({mn, idx});
}

int travelTime(int N, int M, int L, int a[], int b[], int t[]){
    adj.assign(N, vector<pair<int, ll>>());
    dp1.assign(N, {0, -1});
    dp2.assign(N, {0, -1});
    used.assign(N, 0);
    path.clear();

    for(int i = 0; i < M; i++){
        int x = a[i], y = b[i];
        ll z = t[i];
        adj[x].push_back({y, z});
        adj[y].push_back({x, z});
    }

    for(int i = 0; i < N; i++){
        if(!used[i]) prepare(i);
    }

    sort(path.begin(), path.end(), greater<pair<ll, int>> ());
    for(int i = 1; i < path.size(); i++){
        int x = path[i].second, y = path[0].second;
        adj[x].push_back({y, (ll)L});
        adj[y].push_back({x, (ll)L});
    }

    for(int i = 0; i < N; i++){
        dp1[i] = dp2[i] = {0, -1};
    }
    pt.clear();

    dfsf(0, -1);
    dfss(0, -1);

    ll mx = 0;
    for(int i = 0; i < N; i++){
        mx = max(mx, dp1[i].first);
    }

    return mx;
}
//
//int main(void){
//    ios::sync_with_stdio(false);
//    cin.tie(nullptr);
//    int n, m, l;
//    cin >> n >> m >> l;
//    vector<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.data(), B.data(), T.data()) << endl;
//    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