oj.uz

답안 #884033

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
884033 2023-12-06T14:49:22 Z mihtriii295 Putovanje (COCI20_putovanje) C++17
110 / 110
 113 ms 54376 KB 
#include <bits/stdc++.h>

using namespace std;

/* Code by Nguyen Minh Tri (mihtriii) 12TT THPT Chuyen Ben Tre */

#define ll long long 
#define el cout << '\n'

const ll MOD = 998244353;
const ll N = 2e5 + 10000;
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)

ll a[N], b[N], c[N], d[N], h[N], res, par[20][N], n, f[N], fin[N];
vector<ll> adj[N];
map<pair<ll, ll>, ll> mp;

void DFS(ll u, ll p){
    for (ll v : adj[u]){
        if (v == p) continue;
        par[0][v] = u;
        h[v] = h[u] + 1;
        for (ll i = 1; i <= 17; ++i)
            par[i][v] = par[i - 1][par[i - 1][v]];
        DFS(v, u);
    }
}
void DFSin(ll u, ll p){
    fin[u] = f[u];
    for (ll v : adj[u]){
        if (v == p) continue;
        DFSin(v, u);
        fin[u] += fin[v];
    }
}

ll LCA(ll u, ll v){
    if (h[u] < h[v]) swap(u, v);
    ll delta = h[u] - h[v];
    for (ll i = 0; i <= 17; ++i){
        if ((delta >> i) & 1)
            u = par[i][u];
    }
    if (u == v) return u;
    for (ll i = 17; i >= 0; --i){
        if (par[i][u] != par[i][v]){
            u = par[i][u];
            v = par[i][v];
        }
    }
    return par[0][v];
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL);
    cout.tie(NULL);
    if(fopen("coci1920_r5_putovanje.inp", "r")){
        freopen("coci1920_r5_putovanje.inp", "r", stdin);
        freopen("coci1920_r5_putovanje.out", "w", stdout);
    }
    cin >> n;
    for (ll i = 1; i < n; ++i){
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        adj[a[i]].push_back(b[i]);
        adj[b[i]].push_back(a[i]);
    }

    DFS(1, 0);
    for (ll i = 2; i <= n; ++i){
        ll lca = LCA(i, i - 1);
        f[i]++;
        f[i - 1]++;
        f[lca] -= 2;
    }
    DFSin(1, 0);
    for (ll i = 1; i < n; ++i){
        int u = a[i], v = b[i];
        if (h[u] < h[v]) swap(u, v);
        res += min(fin[u] * c[i], d[i]);
    }
    cout << res;
    return 0;
}

Compilation message

putovanje.cpp: In function 'int main()':
putovanje.cpp:58:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |         freopen("coci1920_r5_putovanje.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
putovanje.cpp:59:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |         freopen("coci1920_r5_putovanje.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 43612 KB Output is correct
2 Correct 6 ms 43752 KB Output is correct
3 Correct 7 ms 43792 KB Output is correct
4 Correct 7 ms 43868 KB Output is correct
5 Correct 6 ms 43868 KB Output is correct
6 Correct 7 ms 43748 KB Output is correct
7 Correct 6 ms 43608 KB Output is correct
8 Correct 6 ms 43676 KB Output is correct
9 Correct 6 ms 43868 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 113 ms 52100 KB Output is correct
2 Correct 90 ms 53000 KB Output is correct
3 Correct 85 ms 54376 KB Output is correct
4 Correct 93 ms 53648 KB Output is correct
5 Correct 6 ms 43612 KB Output is correct
6 Correct 73 ms 51796 KB Output is correct
7 Correct 58 ms 50232 KB Output is correct
8 Correct 75 ms 51772 KB Output is correct
9 Correct 52 ms 52104 KB Output is correct
10 Correct 45 ms 51656 KB Output is correct
11 Correct 66 ms 52560 KB Output is correct
12 Correct 52 ms 52456 KB Output is correct

Subtask #3
65.0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 43612 KB Output is correct
2 Correct 6 ms 43752 KB Output is correct
3 Correct 7 ms 43792 KB Output is correct
4 Correct 7 ms 43868 KB Output is correct
5 Correct 6 ms 43868 KB Output is correct
6 Correct 7 ms 43748 KB Output is correct
7 Correct 6 ms 43608 KB Output is correct
8 Correct 6 ms 43676 KB Output is correct
9 Correct 6 ms 43868 KB Output is correct
10 Correct 113 ms 52100 KB Output is correct
11 Correct 90 ms 53000 KB Output is correct
12 Correct 85 ms 54376 KB Output is correct
13 Correct 93 ms 53648 KB Output is correct
14 Correct 6 ms 43612 KB Output is correct
15 Correct 73 ms 51796 KB Output is correct
16 Correct 58 ms 50232 KB Output is correct
17 Correct 75 ms 51772 KB Output is correct
18 Correct 52 ms 52104 KB Output is correct
19 Correct 45 ms 51656 KB Output is correct
20 Correct 66 ms 52560 KB Output is correct
21 Correct 52 ms 52456 KB Output is correct
22 Correct 97 ms 50076 KB Output is correct
23 Correct 74 ms 49184 KB Output is correct
24 Correct 82 ms 49828 KB Output is correct
25 Correct 6 ms 43608 KB Output is correct
26 Correct 35 ms 46424 KB Output is correct
27 Correct 106 ms 49112 KB Output is correct
28 Correct 41 ms 51436 KB Output is correct
29 Correct 52 ms 53400 KB Output is correct
30 Correct 49 ms 52820 KB Output is correct
31 Correct 6 ms 43868 KB Output is correct