oj.uz

Submission #864079

# Submission time Handle Problem Language Result Execution time Memory
864079 2023-10-22T02:17:58 Z amogususus Putovanje (COCI20_putovanje) C++17
25 / 110
 62 ms 36940 KB 
#pragma GCC optimize("Ofast,unroll-loops,inline")
#pragma GCC target("avx2,bmi,bmi2")
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define prec fixed<<setprecision
#define endl '\n'
#define all(x) x.begin(),x.end()
#define pll pair<ll,ll>
#define open(name) if(fopen(name".inp", "r")){freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
using namespace std;
const int maxN=2e5+69;
const int mod=998244353;
ll n,f[maxN],tin[maxN],tout[maxN],timer=0,up[maxN][20];
struct edg{ll v,w,z;};
vector<edg> adj[maxN];
void dfs(int v, int p)
{
    tin[v] = ++timer;
    up[v][0] = p;
    for (int i = 1; i < 20; ++i)
        up[v][i] = up[up[v][i-1]][i-1];
    for (auto [u,_,__] : adj[v])if (u != p)dfs(u, v);
    tout[v] = ++timer;
}
bool is_ancestor(int u, int v)
{
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}

int lca(int u, int v)
{
    if (is_ancestor(u, v))
        return u;
    if (is_ancestor(v, u))
        return v;
    for (int i = 19; i >= 0; --i) {
        if (!is_ancestor(up[u][i], v))
            u = up[u][i];
    }
    return up[u][0];
}
ll pfs[maxN];
ll r=0;
void dfss(ll u,ll p=0){
    for(auto [v,w,c]:adj[u]){
        if(v==p)continue;
        dfss(v,u);
        r+=min(pfs[v]*w,c);
        pfs[u]+=pfs[v];
    }
}
void Enter(){
    cin>>n;
    for(int i=1;i<n;i++){
        ll u,v,w,c;cin>>u>>v>>w>>c;
        adj[u].pb({v,w,c});
        adj[v].pb({u,w,c});
    }
    dfs(1,0);
    for(int i=1;i<n;i++){
        ll x=lca(i,i+1);
        pfs[i]++;
        pfs[i+1]++;
        pfs[x]-=2;
    }
    dfss(1);
    cout<<r;
}
signed main(){
    //open("zzz");
    cin.tie(nullptr);ios_base::sync_with_stdio(NULL);
    //ll t=1;cin>>t;while(t--)
    Enter();
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Incorrect 3 ms 10888 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 32848 KB Output is correct
2 Correct 62 ms 33744 KB Output is correct
3 Correct 58 ms 36940 KB Output is correct
4 Correct 61 ms 36436 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 51 ms 32436 KB Output is correct
7 Correct 33 ms 26196 KB Output is correct
8 Correct 52 ms 32660 KB Output is correct
9 Correct 50 ms 34700 KB Output is correct
10 Correct 48 ms 34640 KB Output is correct
11 Correct 53 ms 35420 KB Output is correct
12 Correct 53 ms 35408 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Incorrect 3 ms 10888 KB Output isn't correct
3 Halted 0 ms 0 KB -