Submission #1141593

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141593		Sang	Dreaming (IOI13_dreaming)	C++20	100 / 100	90 ms	41464 KiB

dreaming

#include<bits/stdc++.h>
#include "dreaming.h"
using namespace std;

#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; i--)
#define fi first
#define se second
#define pb push_back
#define ALL(a) (a).begin(), (a).end()
#define task "kbsiudthw"

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef pair<int, ii> pii;

const int N = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 2277;

int n, m, L, dp[N], mx[N], mi[N], scc;
vector<ii> G[N];

void dfs(int u, int par){
    dp[u] = 0;
    for (ii &v : G[u]){
        if  (v.fi == par) continue;
        dfs(v.fi, u);
        dp[u] = max(dp[u], dp[v.fi] + v.se);
    }
}

void reroot(int u, int par){
    mi[scc] = min(mi[scc], dp[u]);
    mx[scc] = max(mx[scc], dp[u]);

    vector<ii> nodes; nodes.pb({0,0});
    for (ii &x : G[u]) nodes.pb(x);
    vi pref, suff;
    pref = suff = vi(nodes.size() + 3, 0);
    FOR (i, 1, (int)nodes.size() - 1) pref[i] = max(pref[i-1], dp[nodes[i].fi] + nodes[i].se);
    FORD(i, (int)nodes.size() - 1, 1) suff[i] = max(suff[i+1], dp[nodes[i].fi] + nodes[i].se);

    FOR (i, 1, (int)nodes.size() - 1){
        int v = nodes[i].fi;
        if (v == par) continue;
        dp[u] = max(pref[i-1], suff[i+1]);
        dp[v] = max(dp[v], dp[u] + nodes[i].se);
        reroot(v, u);
    }

    dp[u] = pref[(int)nodes.size() - 1];
}

int travelTime(int n, int m, int L, int A[], int B[], int T[]){
    FOR (i, 0, m-1){
        ++A[i]; ++B[i];
        G[A[i]].pb({B[i], T[i]});
        G[B[i]].pb({A[i], T[i]});
    }
    memset(dp, -1, sizeof dp);
    multiset<ii> s;

    FOR(i, 1, n) {
        if (~dp[i]) continue;
        ++scc;
        mi[scc] = 1e9;
        dfs(i, 0);
        reroot(i, 0);
        s.insert({mi[scc], mx[scc]});
    }

    while (s.size() > 1){
        auto it = *s.begin(); s.erase(s.begin());
        auto it2 = *s.rbegin(); s.erase(--s.end());
        ii nw;
        nw.se = max({it.second, it2.second, it.first + it2.first + L});
        nw.fi = min({max(it.first, it2.first + L), max(it2.first, it.first + L)});
        s.insert(nw);
    }
    return s.begin()->second;
}


//signed main(){
//    ios_base::sync_with_stdio(0);
//    cin.tie(0); cout.tie(0);
//    if (fopen(task".inp", "r")){
//        freopen(task".inp", "r", stdin);
//        freopen(task".out", "w", stdout);
//    }
//    cin >> n >> m >> L;
//    FOR (i, 1, m){
//        int u, v, w; cin >> u >> v >> w;
//        ++u;
//        ++v;
//        G[u].pb({v, w});
//        G[v].pb({u, w});
//    }
//    memset(dp, -1, sizeof dp);
//    multiset<ii> s;
//
//    FOR(i,1 , n) {
//        if (~dp[i]) continue;
//        ++scc;
//        mi[scc] = 1e18;
//        dfs(i, 0);
//        reroot(i, 0);
//        s.insert({mi[scc], mx[scc]});
//    }
//
//    while (s.size() > 1){
//        auto it = *s.begin(); s.erase(s.begin());
//        auto it2 = *s.rbegin(); s.erase(--s.end());
//        ii nw;
//        nw.se = max({it.second, it2.second, it.first + it2.first + L});
//        nw.fi = min({max(it.first, it2.first + L), max(it2.first, it.first + L)});
//        s.insert(nw);
//    }
//    cout << s.begin()->second;
//
//    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