oj.uz

Submission #864078

# Submission time Handle Problem Language Result Execution time Memory
864078 2023-10-22T02:10:41 Z amogususus Putovanje (COCI20_putovanje) C++17
25 / 110
 64 ms 38216 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=1e5+69;
const int mod=998244353;
ll n,f[maxN],c[2][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,w,z] : adj[v]) {
        if (u != p){
            dfs(u, v);
            c[0][u]=w;
            c[1][u]=z;
        }
    }

    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];
void dfss(ll u,ll p=0){
    for(auto [v,_,__]:adj[u]){
        if(v==p)continue;
        dfss(v,u);
        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);
    ll r=0;
    for(int i=2;i<=n;i++)r+=min(pfs[i]*c[0][i],c[1][i]);
    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 4440 KB Output is correct
2 Incorrect 2 ms 4700 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 54 ms 34272 KB Output is correct
2 Correct 54 ms 35812 KB Output is correct
3 Correct 63 ms 38216 KB Output is correct
4 Correct 64 ms 37180 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 52 ms 31764 KB Output is correct
7 Correct 35 ms 26196 KB Output is correct
8 Correct 53 ms 34196 KB Output is correct
9 Correct 52 ms 34572 KB Output is correct
10 Correct 50 ms 34128 KB Output is correct
11 Correct 53 ms 35408 KB Output is correct
12 Correct 55 ms 35828 KB Output is correct

Subtask #3
0 / 65.0

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