oj.uz

Submission #460427

# Submission time Handle Problem Language Result Execution time Memory
460427 2021-08-09T06:42:04 Z ak2006 Putovanje (COCI20_putovanje) C++14
110 / 110
 299 ms 59800 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vb = vector<bool>;
using vvb = vector<vb>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vvvl = vector<vvl>;
const ll mod = 1e9 + 7,inf = 1e18;
#define pb push_back
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
void setIO()
{
    fast;
}
ll n = 2e5 + 5,TIMER;
vvvl adj(n);
vvi anc(n,vi(21));
vl pref(n);
vl in(n),out(n),weight1ToParent(n),weight2ToParent(n);
void dfs(int u,int p)
{
    in[u] = ++TIMER;
    anc[u][0] = p;
    for (int i = 1;i<=20;i++)anc[u][i] = anc[anc[u][i - 1]][i - 1];
    for (auto val:adj[u]){
        int v = val[0];
        if (v != p){
            weight1ToParent[v] = val[1];
            weight2ToParent[v] = val[2];
            dfs(v,u);
        }
    }
    out[u] = ++TIMER;
}
void dfs2(int u,int p)
{
    for (auto val:adj[u]){
        int v = val[0];
        if (v != p){
            dfs2(v,u);
            pref[u] += pref[v];
        }
    }
}
bool is_ancestor(int u,int v)
{
    return in[u] <= in[v] && out[u] >= out[v];
}
int LCA(int u,int v)
{
    if (in[u] > in[v])swap(u,v);
    if (is_ancestor(u,v))return u;
    for (int i = 20;i>=0;i--)
        if (!is_ancestor(anc[v][i],u))v = anc[v][i];
    return anc[v][0];
}
int main()
{
    setIO();
    cin>>n;
    for (int i = 1;i<=n - 1;i++){
        int u,v,w1,w2;
        cin>>u>>v>>w1>>w2;
        adj[u].pb({v,w1,w2});
        adj[v].pb({u,w1,w2});
    }
    dfs(1,1);
    for (int i = 1;i<=n - 1;i++){
        int u = i,v = i + 1;
        int l = LCA(u,v);
        // while (u != l){
        //     pref[u]++;
        //     u = anc[u][0];
        // }
        // while (v != l){
        //     pref[v]++;
        //     v = anc[v][0];
        // }

        if (u != l and v != l){
            pref[u]++;
            pref[v]++;
            pref[l]--;
            pref[l]--;
        }
        else{
            if (u == l){
                pref[u]--;
                pref[v]++;
            }
            else{
                pref[v]--;
                pref[u]++;
            }
        }
    }
    dfs2(1,1);
    ll ans = 0;
    for (int i = 2;i<=n;i++)
        ans += min(pref[i] * weight1ToParent[i],weight2ToParent[i]);
    cout<<ans;
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 36300 KB Output is correct
2 Correct 31 ms 36444 KB Output is correct
3 Correct 31 ms 36552 KB Output is correct
4 Correct 32 ms 36560 KB Output is correct
5 Correct 31 ms 36560 KB Output is correct
6 Correct 33 ms 36292 KB Output is correct
7 Correct 28 ms 36300 KB Output is correct
8 Correct 29 ms 36428 KB Output is correct
9 Correct 30 ms 36544 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 55168 KB Output is correct
2 Correct 243 ms 57272 KB Output is correct
3 Correct 273 ms 59800 KB Output is correct
4 Correct 299 ms 58764 KB Output is correct
5 Correct 29 ms 36484 KB Output is correct
6 Correct 239 ms 54612 KB Output is correct
7 Correct 153 ms 50404 KB Output is correct
8 Correct 253 ms 56752 KB Output is correct
9 Correct 150 ms 57000 KB Output is correct
10 Correct 143 ms 56428 KB Output is correct
11 Correct 164 ms 58332 KB Output is correct
12 Correct 162 ms 58412 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 36300 KB Output is correct
2 Correct 31 ms 36444 KB Output is correct
3 Correct 31 ms 36552 KB Output is correct
4 Correct 32 ms 36560 KB Output is correct
5 Correct 31 ms 36560 KB Output is correct
6 Correct 33 ms 36292 KB Output is correct
7 Correct 28 ms 36300 KB Output is correct
8 Correct 29 ms 36428 KB Output is correct
9 Correct 30 ms 36544 KB Output is correct
10 Correct 247 ms 55168 KB Output is correct
11 Correct 243 ms 57272 KB Output is correct
12 Correct 273 ms 59800 KB Output is correct
13 Correct 299 ms 58764 KB Output is correct
14 Correct 29 ms 36484 KB Output is correct
15 Correct 239 ms 54612 KB Output is correct
16 Correct 153 ms 50404 KB Output is correct
17 Correct 253 ms 56752 KB Output is correct
18 Correct 150 ms 57000 KB Output is correct
19 Correct 143 ms 56428 KB Output is correct
20 Correct 164 ms 58332 KB Output is correct
21 Correct 162 ms 58412 KB Output is correct
22 Correct 256 ms 50692 KB Output is correct
23 Correct 239 ms 49004 KB Output is correct
24 Correct 242 ms 50420 KB Output is correct
25 Correct 29 ms 36468 KB Output is correct
26 Correct 114 ms 42632 KB Output is correct
27 Correct 212 ms 48516 KB Output is correct
28 Correct 130 ms 54468 KB Output is correct
29 Correct 176 ms 58428 KB Output is correct
30 Correct 155 ms 58020 KB Output is correct
31 Correct 32 ms 36548 KB Output is correct