oj.uz

답안 #344937

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
344937 2021-01-06T19:16:07 Z limabeans Putovanje (COCI20_putovanje) C++17
110 / 110
 195 ms 26220 KB 
#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;




const int maxn = 2e5 + 10;
const int LOG = 18;

int n;
pair<ll,ll> edge[maxn];
vector<pair<int,int>> g[maxn];


int dep[maxn];
int par[LOG+1][maxn];

void dfs(int at, int p) {
    for (int i=1; i<LOG; i++) {
	par[i][at] = par[i-1][par[i-1][at]];
    }
    
    for (auto ed: g[at]) {
	int to = ed.second;
	if (to == p) continue;
	dep[to]=1+dep[at];
	par[0][to]=at;
	dfs(to,at);
    }
}

ll dp[maxn];

int lca(int u, int v) {
    if (dep[u]<dep[v]) swap(u,v);
    int dx = dep[u]-dep[v];
    for (int i=LOG-1; i>=0; i--) {
	if (dx>>i&1) {
	    u = par[i][u];
	}
    }

    if (u==v) return u;

    for (int i=LOG-1; i>=0; i--) {
	if (par[i][u] != par[i][v]) {
	    u = par[i][u];
	    v = par[i][v];
	}
    }

    return par[0][u];
}


ll edUsage[maxn];

void dfs2(int at, int p) {
    int edId = -1;
    for (auto ed: g[at]) {
	int to = ed.second;
	if (to==p) {
	    edId = ed.first;
	} else {
	    dfs2(to, at);
	}
    }

    if (~edId) {
	edUsage[edId] += dp[at];
	dp[p] += dp[at];
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>n;
    for (int i=0; i<n-1; i++) {
	int u,v; cin>>u>>v;
	int c0,c1;
	cin>>c0>>c1;
	g[u].push_back({i,v});
	g[v].push_back({i,u});
	edge[i] = {c0,c1};
    }

    dfs(1, 0);

    for (int i=1; i<n; i++) {
	int j=i+1;
	int mid = lca(i,j);
	//cout<<i<<"-->"<<j<<": "<<mid<<endl;
	dp[i]++;
	dp[j]++;
	dp[mid]--;
	dp[mid]--;
    }

    dfs2(1, 0);


    ll res = 0;

    for (int i=0; i<n-1; i++) {
	res += min(edge[i].second, edUsage[i]*edge[i].first);
    }


    cout<<res<<endl;



    // for (int i=0; i<n-1; i++) {
    // 	cout<<edUsage[i]<<" ";
    // }
    // cout<<endl;
    
    return 0;
}

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 5 ms 5484 KB Output is correct
3 Correct 5 ms 5504 KB Output is correct
4 Correct 5 ms 5484 KB Output is correct
5 Correct 5 ms 5504 KB Output is correct
6 Correct 5 ms 5356 KB Output is correct
7 Correct 4 ms 5228 KB Output is correct
8 Correct 5 ms 5356 KB Output is correct
9 Correct 5 ms 5484 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 164 ms 23020 KB Output is correct
2 Correct 189 ms 24324 KB Output is correct
3 Correct 173 ms 26220 KB Output is correct
4 Correct 195 ms 25964 KB Output is correct
5 Correct 4 ms 5228 KB Output is correct
6 Correct 174 ms 22764 KB Output is correct
7 Correct 88 ms 18284 KB Output is correct
8 Correct 176 ms 23416 KB Output is correct
9 Correct 78 ms 24044 KB Output is correct
10 Correct 78 ms 23660 KB Output is correct
11 Correct 85 ms 25088 KB Output is correct
12 Correct 98 ms 25324 KB Output is correct

Subtask #3
65.0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 5 ms 5484 KB Output is correct
3 Correct 5 ms 5504 KB Output is correct
4 Correct 5 ms 5484 KB Output is correct
5 Correct 5 ms 5504 KB Output is correct
6 Correct 5 ms 5356 KB Output is correct
7 Correct 4 ms 5228 KB Output is correct
8 Correct 5 ms 5356 KB Output is correct
9 Correct 5 ms 5484 KB Output is correct
10 Correct 164 ms 23020 KB Output is correct
11 Correct 189 ms 24324 KB Output is correct
12 Correct 173 ms 26220 KB Output is correct
13 Correct 195 ms 25964 KB Output is correct
14 Correct 4 ms 5228 KB Output is correct
15 Correct 174 ms 22764 KB Output is correct
16 Correct 88 ms 18284 KB Output is correct
17 Correct 176 ms 23416 KB Output is correct
18 Correct 78 ms 24044 KB Output is correct
19 Correct 78 ms 23660 KB Output is correct
20 Correct 85 ms 25088 KB Output is correct
21 Correct 98 ms 25324 KB Output is correct
22 Correct 159 ms 21228 KB Output is correct
23 Correct 154 ms 19188 KB Output is correct
24 Correct 156 ms 20716 KB Output is correct
25 Correct 4 ms 5356 KB Output is correct
26 Correct 49 ms 12268 KB Output is correct
27 Correct 120 ms 18540 KB Output is correct
28 Correct 70 ms 21788 KB Output is correct
29 Correct 91 ms 25324 KB Output is correct
30 Correct 84 ms 24960 KB Output is correct
31 Correct 5 ms 5484 KB Output is correct