oj.uz

Submission #442851

# Submission time Handle Problem Language Result Execution time Memory
442851 2021-07-09T09:13:01 Z mashrur_hossain Putovanje (COCI20_putovanje) C++17
110 / 110
 243 ms 65044 KB 
#include <bits/stdc++.h>
 
#define fast_cin         ios_base::sync_with_stdio(0); cin.tie(NULL); cerr.tie(NULL);
#define endl "\n"
#define dbg(x) cerr << #x << ": " << x << endl;
#define DBG    cerr << __LINE__ << ": I GOT STUCK\n";
 
using namespace std;    
typedef long long ll;
typedef long double db;
 
struct Edge{
    ll to;
    ll single, multi;
};
 
const ll mxn = 2e5 + 5;
ll n, LOG;
vector<Edge>adj[mxn];
vector<vector<ll>>up(mxn, vector<ll>(20));
ll in[mxn], out[mxn], sub[mxn];
ll timer, ans;
 
void dfs1(ll node, ll par, Edge to_parent){
    for(Edge child: adj[node]){
        if(child.to != par){
            dfs1(child.to, node, child);
            sub[node] += sub[child.to];
        }
    }
    if(par!= 0)ans+= min(sub[node]*to_parent.single, to_parent.multi);
}
 
void dfs2(ll node, ll par){
    in[node] = ++timer;
    up[node][0] = par;
    for(ll i = 1;i<=LOG;i++){
        up[node][i] = up[up[node][i-1]][i-1];
    }
    for(auto child: adj[node]){
        if(child.to != par){
            dfs2(child.to, node);
        }
    }
    out[node] = ++timer;
}
 
bool is_ancestor(ll u, ll v){
    // check if u is an ancestor of v
    return in[u] <= in[v] && out[u] >= out[v];
}
 
ll getlca(ll u, ll v){
    // get lca of u and v;
    if(is_ancestor(u,v))return u;
    if(is_ancestor(v,u))return v;
 
    for(ll i = LOG;i >=0; i--){
        if(!is_ancestor(up[u][i], v))
            u = up[u][i];
    }
    return up[u][0];
}
 
void solve(){
    cin >> n;
    LOG = (ll)log2(n) + 1;
    for(ll i =0;i<n-1;i++){
        ll u, v, c1, c2;
        cin >> u >> v >> c1 >> c2;
        Edge e = {v, c1, c2};
        adj[u].emplace_back(e);
        e.to = u;
        adj[v].emplace_back(e);
    }
 
    dfs2(1,1);
    for(ll i =1;i<n;i++){
        ll lca = getlca(i, i+1);
        if(lca == i){
            sub[i]--;
            sub[i+1]++;
        }
        else if(lca == i+1){
            sub[i]++;
            sub[i+1]--;
        }
        else{
            sub[i] ++;
            sub[i+1]++;
            sub[lca]-=2;
        }
    }
    Edge e = {0, 0, 0};
    dfs1(1, 0, e);
    cout << ans << endl;
}
 
int main() {
    fast_cin;
    int test;test = 1;
    // int test;cin >>test;
    while(test--){
        solve();
    }
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 44148 KB Output is correct
2 Correct 37 ms 44320 KB Output is correct
3 Correct 38 ms 44356 KB Output is correct
4 Correct 41 ms 44384 KB Output is correct
5 Correct 38 ms 44396 KB Output is correct
6 Correct 35 ms 44108 KB Output is correct
7 Correct 37 ms 44200 KB Output is correct
8 Correct 36 ms 44256 KB Output is correct
9 Correct 38 ms 44348 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 60612 KB Output is correct
2 Correct 214 ms 62504 KB Output is correct
3 Correct 237 ms 65044 KB Output is correct
4 Correct 243 ms 63684 KB Output is correct
5 Correct 35 ms 44276 KB Output is correct
6 Correct 229 ms 59964 KB Output is correct
7 Correct 138 ms 56384 KB Output is correct
8 Correct 215 ms 60188 KB Output is correct
9 Correct 129 ms 60520 KB Output is correct
10 Correct 125 ms 59960 KB Output is correct
11 Correct 132 ms 61268 KB Output is correct
12 Correct 137 ms 61524 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 44148 KB Output is correct
2 Correct 37 ms 44320 KB Output is correct
3 Correct 38 ms 44356 KB Output is correct
4 Correct 41 ms 44384 KB Output is correct
5 Correct 38 ms 44396 KB Output is correct
6 Correct 35 ms 44108 KB Output is correct
7 Correct 37 ms 44200 KB Output is correct
8 Correct 36 ms 44256 KB Output is correct
9 Correct 38 ms 44348 KB Output is correct
10 Correct 209 ms 60612 KB Output is correct
11 Correct 214 ms 62504 KB Output is correct
12 Correct 237 ms 65044 KB Output is correct
13 Correct 243 ms 63684 KB Output is correct
14 Correct 35 ms 44276 KB Output is correct
15 Correct 229 ms 59964 KB Output is correct
16 Correct 138 ms 56384 KB Output is correct
17 Correct 215 ms 60188 KB Output is correct
18 Correct 129 ms 60520 KB Output is correct
19 Correct 125 ms 59960 KB Output is correct
20 Correct 132 ms 61268 KB Output is correct
21 Correct 137 ms 61524 KB Output is correct
22 Correct 188 ms 54724 KB Output is correct
23 Correct 157 ms 53476 KB Output is correct
24 Correct 178 ms 54520 KB Output is correct
25 Correct 36 ms 44176 KB Output is correct
26 Correct 91 ms 48712 KB Output is correct
27 Correct 153 ms 53120 KB Output is correct
28 Correct 119 ms 58308 KB Output is correct
29 Correct 142 ms 61620 KB Output is correct
30 Correct 144 ms 61124 KB Output is correct
31 Correct 36 ms 44384 KB Output is correct