Submission #309565

#	Time	Username	Problem	Language	Result	Execution time	Memory
309565		jainbot27	Dreaming (IOI13_dreaming)	C++17	18 / 100	353 ms	19960 KiB

dreaming

#include <bits/stdc++.h>
#ifndef ACMX
#include <dreaming.h>
#endif
using namespace std;

#define f first
#define s second
#define pb push_back
#define ar array
#define all(x) x.begin(), x.end()
#define siz(x) (int)x.size()

#define FOR(x, y, z) for(int x = (y); x < (z); x++)
#define ROF(x, z, y) for(int x = (y-1); x >= (z); x--)
#define F0R(x, z) FOR(x, 0, z)
#define R0F(x, z) ROF(x, 0, z)
#define trav(x, y) for(auto&x:y)

using ll = long long;
using vi = vector<int>;
using vl = vector<long long>;
using pii = pair<int, int>;
using vpii = vector<pair<int, int>>;

template<class T> inline bool ckmin(T&a, T b) {return b < a ? a = b, 1 : 0;}
template<class T> inline bool ckmax(T&a, T b) {return b > a ? a = b, 1 : 0;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const char nl = '\n';
const int mxN = 100010;
const int MOD = 1e9 + 7;
const long long infLL = 1e18;

using node = ll;
 
struct lazy{
    int size;
    vector<node> operations;
    vector<node> vals;
    const node NEUTRAL_ELEMENT = 0;
    const node NO_OPERATION = 0;
    const node START_VAL = 0;
    ll query_op(node a, node b, int len){
        return a + b;
    }
    ll calc_op(node a, node b){
        return max(a, b);
    }
    void apply_mod_op(node & a, node b, int c){
        a = query_op(a, b, c);
    }
    void propogate(int x, int lx, int rx){
        if(rx - lx == 1) return;
        int m = (lx + rx)/2;
        apply_mod_op(operations[2*x+1], operations[x], 1);
        apply_mod_op(vals[2*x+1], operations[x], m-lx);
        apply_mod_op(operations[2*x+2], operations[x], 1);
        apply_mod_op(vals[2*x+2], operations[x], rx-m);
        operations[x] = NO_OPERATION;
    }
    void build(int x, int lx, int rx){
        if(rx == lx + 1){
            vals[x] = START_VAL;
            return;
        }
        int m = (lx + rx)/2;
        build(2*x + 1, lx, m);
        build(2*x + 2, m, rx);
        vals[x] = calc_op(vals[x * 2 + 1], vals[x * 2 + 2]);
    }
    void init(int n){
        size = 1;
        while(size < n) size *= 2;
        operations.assign(2 * size, 0);
        vals.assign(2 * size, 0);
        // build(0, 0, size);
    }
    void update(int l, int r, node v, int x, int lx, int rx){
        propogate(x, lx, rx);
        if(lx >= r || l >= rx) return;
        if(lx >= l && rx <= r){
            apply_mod_op(operations[x], v, 1);
            apply_mod_op(vals[x], v, rx - lx);
            return;
        }
        int m = (lx + rx)/2;
        update(l, r, v, 2 * x + 1, lx , m);
        update(l, r, v, 2 * x + 2, m , rx);
        vals[x] = calc_op(vals[x * 2 + 1], vals[x * 2 + 2]);
    }
    void update(int l, int r, ll v){
        update(l, r, v, 0, 0, size);
    }
    node query(int l, int r, int x, int lx, int rx){
        propogate(x, lx, rx);
        if(lx >= r || l >= rx) return NEUTRAL_ELEMENT;
        if(lx >= l && rx <= r){
            return vals[x];
        }
        int m = (lx + rx)/2;
        node m1 = query(l, r, 2 * x + 1, lx, m);
        node m2 = query(l, r, 2 * x + 2, m, rx);
        return calc_op(m1, m2);
    }
    node query(int l , int r){
        return query(l, r, 0, 0, size);
    }
};

vpii adj[mxN]; 
int n, m, l, ctr, eu1[mxN], eu2[mxN], d[mxN], bst;
vi a, b, t, cur, coms;
bool vis[mxN];

void dfs(int u, int p, int dist){
    vis[u] = 1;
    eu1[u] = ctr;
    eu2[u] = ctr;
    ctr++;
    d[u] = dist;
    cur.pb(u);
    trav(v, adj[u]){
        if(v.f==p)
            continue;
        dfs(v.f, u, v.s + dist);
        ckmax(eu2[u], eu2[v.f]);
    }
}
void dfs2(int u, int p, int dist, lazy&st){
    st.update(eu1[u], eu2[u]+1, -2*dist);
    st.update(0, ctr, dist);
    // cout << u << " " << p << " " << dist << " " << st.query(0, ctr) << endl;
    ckmin(bst, (int)st.query(0, ctr));
    trav(v, adj[u]){
        if(v.f == p) 
            continue;
        dfs2(v.f, u, v.s, st);
    }
    st.update(eu1[u], eu2[u]+1, 2*dist);
    st.update(0, ctr, -dist);
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]){
    n = N, m = M, l = L;
    // cout << n << m << l << endl;
    a = b = t = vi(m);
    F0R(i, m){
        a[i] = A[i];
        b[i] = B[i];
        t[i] = T[i];
    }
    // cout << "WE GOT HERE" << endl;
    F0R(i, m){
        adj[a[i]].pb({b[i], t[i]});
        adj[b[i]].pb({a[i], t[i]});
    }
    F0R(i, n){
        if(vis[i]) 
            continue;
        ctr = 0;
        cur.clear();
        bst = MOD;
        dfs(i, -1, 0);
        lazy st;
        st.init(ctr);
        // cout << i << nl;
        trav(x, cur){
            // cout << x << " " << d[x] << nl;
            st.update(eu1[x], eu1[x]+1, d[x]);
        }
        dfs2(i, -1, 0, st);
        coms.pb(bst);
    }
    sort(all(coms));
    if(siz(coms)==1){
        return coms.back();
    }
    else if(siz(coms)==2){
        return coms[0] + coms[1] + L;
    }
    else{
        return max(coms[siz(coms)-1]+coms[siz(coms)-2]+L, coms[siz(coms)-3]+coms[siz(coms)-2]+2*L);
    }
}

// int32_t main(){
//     ios_base::sync_with_stdio(0); cin.tie(0);
//     int N, M, K; 
//     cin >> N >> M >> K;
//     int A[M], B[M], T[M];
//     F0R(i, M){
//         cin >> A[i] >> B[i] >> T[i];
//     }
//     int res = travelTime(N, M, K, A, B, T);
//     cout << res << nl;
//     return 0;
// }

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