# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
224199 | 2020-04-17T12:23:10 Z | jamielim | Putovanje (COCI20_putovanje) | C++14 | 172 ms | 36340 KB |
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair <int,int> pii; typedef pair <ll, ll> pll; const int MAXN = 200100; int n; struct UnionFind { vector <int> v[MAXN]; int connected[MAXN],par[MAXN]; void init() { for(int i=0;i<MAXN;i++){ v[i].clear();v[i].push_back(i); par[i]=i; connected[i]=0; } } void merge(int a, int b) { a = par[a];b = par[b]; if ((int)v[a].size() < (int)v[b].size()) swap(a, b); //merging smaller into larger for (auto x : v[b]) { if (par[x - 1] == a) connected[a]++; if (par[x + 1] == a) connected[a]++; v[a].push_back(x); } for (auto x : v[b]) par[x] = a; connected[a] += connected[b]; } int get(int x) { //number of times the edge from x to its parent (original tree) is used x = par[x]; int ret = ((int)v[x].size() - connected[x]) * 2; if (par[1] == x) ret--; if (par[n] == x) ret--; return ret; } }Uf; int c[MAXN],d[MAXN],cnt[MAXN]; vector<pii> adj[MAXN]; void dfs(int x,int p,int idx){ for(int i=0;i<(int)adj[x].size();i++){ if(adj[x][i].first==p)continue; dfs(adj[x][i].first,x,adj[x][i].second); Uf.merge(x,adj[x][i].first); } if(idx!=-1)cnt[idx]=Uf.get(x); } int main(){ scanf("%d",&n); int a,b; for(int i=0;i<n-1;i++){ scanf("%d%d%d%d",&a,&b,&c[i],&d[i]); adj[a].push_back(make_pair(b,i));adj[b].push_back(make_pair(a,i)); } Uf.init(); dfs(1,-1,-1); ll ans=0; for(int i=0;i<n-1;i++)ans+=min((ll)c[i]*(ll)cnt[i],(ll)d[i]); printf("%lld",ans); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 26 ms | 17536 KB | Output is correct |
2 | Correct | 27 ms | 17656 KB | Output is correct |
3 | Correct | 27 ms | 17664 KB | Output is correct |
4 | Correct | 27 ms | 17792 KB | Output is correct |
5 | Correct | 25 ms | 17792 KB | Output is correct |
6 | Correct | 23 ms | 17664 KB | Output is correct |
7 | Correct | 23 ms | 17664 KB | Output is correct |
8 | Correct | 26 ms | 17664 KB | Output is correct |
9 | Correct | 27 ms | 17792 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 123 ms | 31348 KB | Output is correct |
2 | Correct | 143 ms | 33780 KB | Output is correct |
3 | Correct | 121 ms | 36340 KB | Output is correct |
4 | Correct | 144 ms | 34804 KB | Output is correct |
5 | Correct | 26 ms | 17664 KB | Output is correct |
6 | Correct | 118 ms | 31488 KB | Output is correct |
7 | Correct | 83 ms | 28384 KB | Output is correct |
8 | Correct | 111 ms | 31452 KB | Output is correct |
9 | Correct | 85 ms | 31348 KB | Output is correct |
10 | Correct | 85 ms | 30964 KB | Output is correct |
11 | Correct | 89 ms | 32116 KB | Output is correct |
12 | Correct | 88 ms | 32244 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 26 ms | 17536 KB | Output is correct |
2 | Correct | 27 ms | 17656 KB | Output is correct |
3 | Correct | 27 ms | 17664 KB | Output is correct |
4 | Correct | 27 ms | 17792 KB | Output is correct |
5 | Correct | 25 ms | 17792 KB | Output is correct |
6 | Correct | 23 ms | 17664 KB | Output is correct |
7 | Correct | 23 ms | 17664 KB | Output is correct |
8 | Correct | 26 ms | 17664 KB | Output is correct |
9 | Correct | 27 ms | 17792 KB | Output is correct |
10 | Correct | 123 ms | 31348 KB | Output is correct |
11 | Correct | 143 ms | 33780 KB | Output is correct |
12 | Correct | 121 ms | 36340 KB | Output is correct |
13 | Correct | 144 ms | 34804 KB | Output is correct |
14 | Correct | 26 ms | 17664 KB | Output is correct |
15 | Correct | 118 ms | 31488 KB | Output is correct |
16 | Correct | 83 ms | 28384 KB | Output is correct |
17 | Correct | 111 ms | 31452 KB | Output is correct |
18 | Correct | 85 ms | 31348 KB | Output is correct |
19 | Correct | 85 ms | 30964 KB | Output is correct |
20 | Correct | 89 ms | 32116 KB | Output is correct |
21 | Correct | 88 ms | 32244 KB | Output is correct |
22 | Correct | 137 ms | 26584 KB | Output is correct |
23 | Correct | 121 ms | 25592 KB | Output is correct |
24 | Correct | 172 ms | 26352 KB | Output is correct |
25 | Correct | 28 ms | 17656 KB | Output is correct |
26 | Correct | 80 ms | 21364 KB | Output is correct |
27 | Correct | 117 ms | 25416 KB | Output is correct |
28 | Correct | 86 ms | 29684 KB | Output is correct |
29 | Correct | 95 ms | 32240 KB | Output is correct |
30 | Correct | 98 ms | 31988 KB | Output is correct |
31 | Correct | 29 ms | 17792 KB | Output is correct |