Submission #1282956

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282956		baotoan655	Dreaming (IOI13_dreaming)	C++20	100 / 100	162 ms	19980 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
#define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
using namespace std;

const int N = 1e5 + 5;
struct node {
    int mx, lazy;
    node() {
        mx = 0;
        lazy = 0;
    }
    node operator + (const node& o) const {
        node res;
        res.mx = max(mx, o.mx);
        return res;
    }
};
node it[N << 2];
void upd(int k, int val) {
    it[k].lazy += val;
    it[k].mx += val;
}
void shift(int k) {
    upd(k << 1, it[k].lazy);
    upd(k << 1 | 1, it[k].lazy);
    it[k].lazy = 0;
}
void update(int k, int l, int r, int u, int v, int val) {
    if(l > v || r < u) return;
    if(u <= l && r <= v) {
        upd(k, val);
        return;
    }
    shift(k);
    int mid = l + r >> 1;
    update(k << 1, l, mid, u, v, val);
    update(k << 1 | 1, mid + 1, r, u, v, val);
    it[k] = it[k << 1] + it[k << 1 | 1];
}
int n, m, L;
vector<pair<int, int>> g[N];
int comps, id[N];
vector<int> ve;
vector<int> lens;
int in[N], out[N], tim;
int dist[N];
int cnt;
int dia;
void dfs(int u) {
    id[u] = comps;
    ve.emplace_back(u);
    for(auto [v, w] : g[u]) if(id[v] != comps) {
            dfs(v);
        }
}
void cal(int u, int p) {
    in[u] = ++tim;
    for(auto [v, w] : g[u]) if(v != p) {
            dist[v] = dist[u] + w;
            cal(v, u);
        }
    out[u] = tim;
}
int best;
void reroot(int u, int p) {
    best = min(best, it[1].mx);
    dia = max(dia, it[1].mx);
    for(auto [v, w] : g[u]) if(v != p) {
            update(1, 1, cnt, 1, cnt, w);
            update(1, 1, cnt, in[v], out[v], -2 * w);
            reroot(v, u);
            update(1, 1, cnt, 1, cnt, -w);
            update(1, 1, cnt, in[v], out[v], 2 * w);
        }
}
int travelTime(int _n, int _m, int _L, int A[], int B[], int T[]) {
    n = _n;
    m = _m;
    L = _L;
    for(int i = 0; i < m; ++i) {
        g[A[i] + 1].emplace_back(B[i] + 1, T[i]);
        g[B[i] + 1].emplace_back(A[i] + 1, T[i]);
    }
    for(int i = 1; i <= n; ++i) if(!id[i]) {
            ++comps;
            ve.clear();
            dfs(i);
            cnt = ve.size();
            dist[ve[0]] = 0;
            tim = 0;
            cal(ve[0], 0);
            for(int j = 0; j <= cnt * 4 + 5; ++j) it[j] = node();
            for(int x : ve) update(1, 1, cnt, in[x], in[x], dist[x]);
            best = 2e9;
            reroot(ve[0], 0);
            lens.emplace_back(best);
        }
    sort(lens.rbegin(), lens.rend());
    if((int)lens.size() == 1) return dia;
    if(lens.size() == 2) return max(dia, lens[0] + lens[1] + L);
    return max(dia, max(lens[0] + lens[1] + L, lens[1] + lens[2] + 2 * L));

}

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