Submission #311694

#	Time	Username	Problem	Language	Result	Execution time	Memory
311694		thecodingwizard	Putovanje (COCI20_putovanje)	C++11	110 / 110	221 ms	23288 KiB

putovanje

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define ii pair<int, int>
#define f first
#define s second
#define mp make_pair
#define pb push_back

int n; 
vector<pair<int, ii>> adj[200000];
int pa[200000][20];
int depth[200000];
int in[200000], out[200000], ctr = 0;

void dfs(int u, int p, int d) {
    in[u] = ctr++;
    pa[u][0] = p;
    depth[u] = d;
    for (auto v : adj[u]) {
        if (v.f != p) dfs(v.f, u, d+1);
    }
    out[u] = ctr-1;
}

int lca(int a, int b) {
    if (depth[a] < depth[b]) swap(a, b);
    for (int i = 19; i >= 0; i--) {
        if (depth[pa[a][i]] >= depth[b]) a = pa[a][i];
    }
    if (a == b) return a;
    for (int i = 19; i >= 0; i--) {
        if (pa[a][i] != pa[b][i]) {
            a = pa[a][i], b = pa[b][i];
        }
    }
    return pa[a][0];
}

int ft[200001];
void upd(int k, int v) {
    k++;
    while (k <= 200000) {
        ft[k] += v;
        k += k&-k;
    }
}
int qry(int k) {
    k++;
    int ans = 0;
    while(k) {
        ans += ft[k];
        k -= k&-k;
    }
    return ans;
}

ll ans = 0;
void dfs2(int u, int p) {
    for (auto v : adj[u]) {
        if (v.f == p) continue;
        assert(depth[v.f] = depth[u]+1);
        ll numTraversals = qry(out[v.f]) - qry(in[v.f]-1);
        //cout << u << "->" << v.f << ": " << min(numTraversals*v.s.f, (ll)v.s.s) << endl;
        ans += min(numTraversals*v.s.f, (ll)v.s.s);
        dfs2(v.f, u);
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;

    for (int i = 0; i < n-1; i++) {
        int a, b, c, d; cin >> a >> b >> c >> d; --a; --b;
        adj[a].push_back(mp(b, mp(c, d)));
        adj[b].push_back(mp(a, mp(c, d)));
    }

    dfs(0, 0, 0);

    for (int j = 1; j < 20; j++) {
        for (int i = 0; i < n; i++) {
            pa[i][j] = pa[pa[i][j-1]][j-1];
        }
    }

    for (int i = 0; i < n-1; i++) {
        int x = lca(i, i+1);
        assert(depth[i] >= depth[x]);
        assert(depth[i+1] >= depth[x]);
        upd(in[i], 1);
        upd(in[i+1], 1);
        upd(in[x], -2);
    }

    dfs2(0, 0);
    cout << ans << endl;

    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 25 / 25
• Subtask 3: 65 / 65