Submission #982332

#	Time	Username	Problem	Language	Result	Execution time	Memory
982332		kwongweng	Dreaming (IOI13_dreaming)	C++17	100 / 100	170 ms	31228 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long double ld;
typedef vector<vector<ll>> vll;
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define ms memset
#define fi first
#define se second

struct segtree{
    vi tl, tr, mx, op; int sz;
    void build(int v, int l, int r){
        tl[v]=l; tr[v]=r;
        if (l==r) return;
        int tm = (l+r)/2;
        build(2*v,l,tm); build(2*v+1,tm+1,r);
    }
    void init(int n){
        sz=n;
        tl.assign(4*n,0); tr.assign(4*n,0);
        mx.assign(4*n,0); op.assign(4*n,0);
        build(1,0,n-1);
    }
    void prop(int v){
        if (tl[v]==tr[v]){op[v]=0; return;}
        int tm = (tl[v]+tr[v])/2;
        op[2*v] += op[v]; mx[2*v] += op[v];
        op[2*v+1] += op[v]; mx[2*v+1] += op[v];
        op[v] = 0;
    }
    void upd(int v, int l, int r, int val){
        //prop(v);
        if (tl[v]==l && tr[v]==r){
            op[v] += val; mx[v] += val;
            return;
        }
        if (l>r) return;
        int tm = (tl[v]+tr[v])/2;
        upd(2*v,l,min(r,tm),val);
        upd(2*v+1,max(l,tm+1),r,val);
        mx[v] = max(mx[2*v],mx[2*v+1]) + op[v];
    }
};

const int mxn = 1e5+1;
vii g[mxn];
vi p(mxn), dist(mxn), tin(mxn), sz(mxn);
vi mx_dist(mxn);
vi CC[mxn]; int cc_num = 0;

int cur = 0;
void dfs(int u){
    CC[cc_num].pb(u);
    tin[u] = cur; cur++;
    sz[u] = 1;
    for (ii e : g[u]){
        int v = e.fi;
        if (p[u] == v) continue;
        dist[v] = dist[u] + e.se; p[v] = u;
        dfs(v);
        sz[u] += sz[v];
    }
}

segtree st;
int n;
void get_mx(int u){
    mx_dist[u] = st.mx[1];
    for (ii e : g[u]){
        int v = e.fi, w = e.se;
        if (p[u]==v) continue;
        st.upd(1,0,tin[v]-1,w); st.upd(1,tin[v],tin[v]+sz[v]-1,-w); st.upd(1,tin[v]+sz[v],n-1,w);
        get_mx(v);
        st.upd(1,0,tin[v]-1,-w); st.upd(1,tin[v],tin[v]+sz[v]-1,w); st.upd(1,tin[v]+sz[v],n-1,-w);
    }
}


int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    n = N;
    vi used(N);
    int ans = 0;
    vi costs;
    FOR(i,0,M){
        g[A[i]].pb({B[i],T[i]}); g[B[i]].pb({A[i],T[i]});
    }
    FOR(i,0,N){
        if (used[i]) continue;
        used[i] = 1; cc_num++;
        cur = 0;
        dfs(i); st.init(sz[i]); n = sz[i];
        FOR(j,0,sz[i]){
            int v = CC[cc_num][j]; used[v]=1;
            st.upd(1,tin[v],tin[v],dist[v]);
        }
        
        get_mx(i);
        int mn = mx_dist[i];
        FOR(j,0,sz[i]){
            int v = CC[cc_num][j];
            mn = min(mn, mx_dist[v]);
        }
        costs.pb(mn);
    }
    FOR(i,0,N) ans = max(ans, mx_dist[i]);
    sort(costs.rbegin(), costs.rend());
    if (N-M==1) return ans;
    if (N-M==2) return max(ans,L + costs[0] + costs[1]);
    return max(ans,max(L+costs[0]+costs[1],2*L+costs[1]+costs[2]));
}

Compilation message (stderr)

dreaming.cpp: In member function 'void segtree::prop(int)':
dreaming.cpp:33:13: warning: unused variable 'tm' [-Wunused-variable]
   33 |         int tm = (tl[v]+tr[v])/2;
      |             ^~

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