Submission #250042

#	Time	Username	Problem	Language	Result	Execution time	Memory
250042		MarcoMeijer	Dreaming (IOI13_dreaming)	C++14	100 / 100	144 ms	24952 KiB

dreaming

#include "dreaming.h"

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

//macros
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define INF 1e9
#define pb push_back
#define fi first
#define se second

const int MX = 3e5;

int n, m, l;
vii adj[MX];
ii len[MX];
bitset<MX> visited;

ii push(ii p, int v) {
    return {max(p.fi,v), max(min(p.fi,v),p.se)};
}
void dfsSize(int u, int p=-1) {
    visited[u] = 1;
    len[u] = {0, 0};
    for(ii v:adj[u]) if(v.fi!=p) dfsSize(v.fi,u), len[u] = push(len[u], v.se+len[v.fi].fi);
}
ii getShortest(int u, int p=-1, int top = 0) {
    ii ans = {max(top, len[u].fi), u};
    for(ii v:adj[u]) if(v.fi!=p) {
        int nTop = v.se + top;
        if(len[u].fi == v.se+len[v.fi].fi)  nTop = max(nTop, v.se + len[u].se);
        else                                nTop = max(nTop, v.se + len[u].fi);
        ans = min(ans, getShortest(v.fi, u, nTop));
    }
    return ans;
}

ii dfsFurthest(int u, int p=-1, int d=0) {
    ii ans = {d,u};
    for(ii v:adj[u]) if(v.fi!=p) ans = max(ans, dfsFurthest(v.fi, u, v.se+d));
    return ans;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    n=N, m=M, l=L;
    RE(i,m) adj[A[i]].pb({B[i], T[i]});
    RE(i,m) adj[B[i]].pb({A[i], T[i]});

    priority_queue<ii> pq;

    visited.reset();
    RE(u,n) {
        if(visited[u]) continue;
        dfsSize(u);
        ii p = getShortest(u);
        pq.push(p);
    }

    int u = pq.top().se; pq.pop();
    while(!pq.empty()) {
        int v = pq.top().se; pq.pop();
        adj[u].pb({v, l});
        adj[v].pb({u, l});
    }

    ii p = dfsFurthest(0);
    return dfsFurthest(p.se).fi;
}

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