oj.uz

Submission #649597

# Submission time Handle Problem Language Result Execution time Memory
649597 2022-10-11T02:57:58 Z AkiYuu Putovanje (COCI20_putovanje) C++17
25 / 110
 99 ms 47768 KB 
/*

Author: AkiYuu
TASK:
LANG: C++14

*/

#include <bits/stdc++.h>
#define task "GROUP"
#define ll long long
#define ld long double
#define pb push_back
#define ffw(i,a,b) for (ll i = a; i <= b; i++)
#define fbw(i,b,a) for (ll i = b; i >= a; i--)
#define adj(v,adj,u) for (auto v : adj[u])
#define rep(i,a) for (auto i : a)
#define reset(a) memset(a, 0, sizeof(a))
#define sz(a) a.size()
#define all(a) a.begin(),a.end()

using namespace std;

void fastio(){
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
//	freopen(task".inp", "r", stdin);
//	freopen(task".out", "w", stdout);
}

const int mxn = 1e6 + 5;
typedef pair<ll, ll> ii;

vector < ii > a[mxn];
int up[20][mxn], tin[mxn], tout[mxn], timer;
ll add[mxn];
int n;
ll cost[2][mxn];
int edge[mxn];
ll ans = 0;

void dfs(int u, int p ){
    tin[u] = ++timer;
    up[0][u] = p;

    for ( ii x : a[u]){
        int v = x.first, id = x.second;
        if ( v == p ) continue;
        dfs(v,u);
        edge[v] = id;
    }

    tout[u] = timer;
}

bool ispar(int u , int v){
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}

int lca(int u, int v){
    if (ispar(u,v) ) return u;
    if (ispar(v,u) )  return v;
    fbw(i,18,0) if (!ispar(up[i][u], v)) u= up[i][u];
    return up[0][u];
}

void get(int u, int p = -1){

    for ( ii x : a[u]) {

        int v = x.first, id = x.second;
        if (v == p ) continue;
        get(v,u);
        add[u] += add[v];
    }
    int Eid = edge[u];
    ans += min( cost[0][Eid] * add[u], cost[1][Eid] );

}

void solve(){

    cin >> n;

    ffw(i,1,n-1){
        int u , v;
        cin >> u >> v >> cost[0][i] >> cost[1][i];
        a[u].pb(ii(v,i));
        a[v].pb(ii(u,i));
    }

    dfs(1,1);
    ffw(i,1,n-1){
        int u    = i, v = i  +1, c= lca(u,v);
        add[u]++;
        add[v]++;
        add[c] -= 2;
    }

    ffw(i,1,18) ffw(j,1,n){
        up[i][j] = up[i-1][ up[i-1][j] ];
    }

    get(1);
    cout << ans;
}

int main(){
	fastio();
	int t = 1;
//	cin >> t;
	while (t--)
	solve();
}

Compilation message

putovanje.cpp: In function 'void get(int, int)':
putovanje.cpp:71:26: warning: unused variable 'id' [-Wunused-variable]
   71 |         int v = x.first, id = x.second;
      |                          ^~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23892 KB Output is correct
2 Incorrect 17 ms 24256 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 99 ms 43740 KB Output is correct
2 Correct 75 ms 45148 KB Output is correct
3 Correct 78 ms 47768 KB Output is correct
4 Correct 91 ms 47280 KB Output is correct
5 Correct 16 ms 24020 KB Output is correct
6 Correct 79 ms 43340 KB Output is correct
7 Correct 53 ms 38148 KB Output is correct
8 Correct 81 ms 43756 KB Output is correct
9 Correct 74 ms 44748 KB Output is correct
10 Correct 68 ms 44084 KB Output is correct
11 Correct 71 ms 45772 KB Output is correct
12 Correct 77 ms 45976 KB Output is correct

Subtask #3
0 / 65.0

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