oj.uz

답안 #852288

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
852288 2023-09-21T14:19:07 Z hungnt Putovanje (COCI20_putovanje) C++14
110 / 110
 77 ms 34736 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;

const int N = 200005;

int n;
long long c[N], d[N];
int h[N], par[N][25], dp[N], cnt[N], s[N];
vector<pair<int, int>> adj[N];

void dfs(int u, int p, int t)
{
    h[u] = t;
    par[u][0] = p;
    for(auto v : adj[u])
        if(v.fi != p)
            dfs(v.fi, u, t + 1);
}

int lca(int u, int v)
{
    if(h[u] < h[v]) swap(u, v);
    int diff = h[u] - h[v];
    for(int i = 20; i >= 0; i--)
        if(diff & (1 << i))
            u = par[u][i];
    if(u == v) return u;
    for(int i = 20; i >= 0; i--)
        if(par[u][i] != par[v][i])
        {
            u = par[u][i];
            v = par[v][i];

        }
    return par[v][0];
}

void calc(int u, int p, int id)
{
    for(auto x : adj[u])
        if(x.fi != p)
        {
            calc(x.fi, u, x.se);
            dp[u] += dp[x.first];
        }
    dp[u] += s[u];
    cnt[id] = dp[u];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin >> n;
    int u, v;
    for(int i = 1; i < n; i++)
    {
        cin >> u >> v >> c[i] >> d[i];
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
    }
    dfs(1, 0, 0);
    for(int i = 1; (1 << i) <= n; i++)
        for(int j = 1; j <= n; j++)
            par[j][i] = par[par[j][i - 1]][i - 1];
    for(int i = 1; i < n; i++)
    {
        s[i]++;
        s[i + 1]++;
        s[lca(i, i + 1)] -= 2;
    }
    calc(1, 0, 0);
    long long ans = 0;
    for(int i = 1; i <= n; i++)
        ans += min(cnt[i] * c[i], d[i]);
    cout << ans;
}

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Correct 3 ms 12888 KB Output is correct
3 Correct 3 ms 12892 KB Output is correct
4 Correct 4 ms 13044 KB Output is correct
5 Correct 4 ms 12956 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct
7 Correct 2 ms 12892 KB Output is correct
8 Correct 3 ms 12892 KB Output is correct
9 Correct 3 ms 12888 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 65 ms 30544 KB Output is correct
2 Correct 77 ms 31912 KB Output is correct
3 Correct 75 ms 33620 KB Output is correct
4 Correct 74 ms 34736 KB Output is correct
5 Correct 3 ms 12892 KB Output is correct
6 Correct 61 ms 30480 KB Output is correct
7 Correct 40 ms 26192 KB Output is correct
8 Correct 69 ms 30384 KB Output is correct
9 Correct 47 ms 30544 KB Output is correct
10 Correct 45 ms 30492 KB Output is correct
11 Correct 64 ms 33104 KB Output is correct
12 Correct 58 ms 33304 KB Output is correct

Subtask #3
65.0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Correct 3 ms 12888 KB Output is correct
3 Correct 3 ms 12892 KB Output is correct
4 Correct 4 ms 13044 KB Output is correct
5 Correct 4 ms 12956 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct
7 Correct 2 ms 12892 KB Output is correct
8 Correct 3 ms 12892 KB Output is correct
9 Correct 3 ms 12888 KB Output is correct
10 Correct 65 ms 30544 KB Output is correct
11 Correct 77 ms 31912 KB Output is correct
12 Correct 75 ms 33620 KB Output is correct
13 Correct 74 ms 34736 KB Output is correct
14 Correct 3 ms 12892 KB Output is correct
15 Correct 61 ms 30480 KB Output is correct
16 Correct 40 ms 26192 KB Output is correct
17 Correct 69 ms 30384 KB Output is correct
18 Correct 47 ms 30544 KB Output is correct
19 Correct 45 ms 30492 KB Output is correct
20 Correct 64 ms 33104 KB Output is correct
21 Correct 58 ms 33304 KB Output is correct
22 Correct 65 ms 27472 KB Output is correct
23 Correct 61 ms 26804 KB Output is correct
24 Correct 60 ms 27216 KB Output is correct
25 Correct 2 ms 12888 KB Output is correct
26 Correct 30 ms 19536 KB Output is correct
27 Correct 49 ms 26448 KB Output is correct
28 Correct 41 ms 29300 KB Output is correct
29 Correct 53 ms 33360 KB Output is correct
30 Correct 50 ms 33616 KB Output is correct
31 Correct 3 ms 12888 KB Output is correct