oj.uz

Submission #201444

# Submission time Handle Problem Language Result Execution time Memory
201444 2020-02-10T15:01:29 Z ami Putovanje (COCI20_putovanje) C++17
110 / 110
 338 ms 35928 KB 
#include <bits/stdc++.h>
#define sz(c)       int(c.size())
#define rep(i,a,b)  for (int i=a; i<(b); ++i)
#define per(i,a,b)  for (int i=(b)-1; i>=(a); --i)
#define fore(c,...) for (auto __VA_ARGS__:(c))
using namespace std;
typedef long long ll;



int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	cout<<fixed<<setprecision(10);

	int N;
	cin>>N;
	vector<vector<pair<int,int>>> adj(N);
	vector<pair<int,int>> cost(N-1);
	rep(i,0,N-1) {
		int a,b,c1,c2;
		cin>>a>>b>>c1>>c2;
		a--,b--;
		adj[a].emplace_back(b,i);
		adj[b].emplace_back(a,i);
		cost[i]={c1,c2};
	}

	vector<ll> cnt(N-1);
	vector<set<pair<int,bool>>> s(N);
	function<void(int,int)> dfs=[&](int v,int p) {
		if (v>0) s[v].emplace(v,false);
		if (v<N-1) s[v].emplace(v,true);

		int k=-1;
		fore(adj[v],e) {
			int u=e.first;
			if (u==p) {
				k=e.second;
				continue;
			}

			dfs(u,v);
			if (sz(s[v])<sz(s[u])) s[v].swap(s[u]);
			fore(s[u],t) {
				pair<int,bool> x={t.first,!t.second};
				if (t.second) x.first++; else x.first--;
				auto it=s[v].find(x);
				if (it!=s[v].end()) s[v].erase(it); else s[v].insert(t);
			}
			set<pair<int,bool>>().swap(s[u]);
		}
		if (k!=-1) cnt[k]+=sz(s[v]);
	};

	dfs(0,-1);


	ll res=0;
	rep(i,0,N-1) res+=min(cost[i].first*cnt[i],(ll)cost[i].second);
	cout<<res<<'\n';
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 7 ms 632 KB Output is correct
3 Correct 10 ms 632 KB Output is correct
4 Correct 10 ms 632 KB Output is correct
5 Correct 10 ms 632 KB Output is correct
6 Correct 6 ms 376 KB Output is correct
7 Correct 6 ms 504 KB Output is correct
8 Correct 8 ms 504 KB Output is correct
9 Correct 8 ms 632 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 28536 KB Output is correct
2 Correct 191 ms 30696 KB Output is correct
3 Correct 223 ms 35928 KB Output is correct
4 Correct 224 ms 33760 KB Output is correct
5 Correct 7 ms 504 KB Output is correct
6 Correct 191 ms 25848 KB Output is correct
7 Correct 139 ms 20728 KB Output is correct
8 Correct 209 ms 25996 KB Output is correct
9 Correct 167 ms 29436 KB Output is correct
10 Correct 172 ms 28664 KB Output is correct
11 Correct 173 ms 30844 KB Output is correct
12 Correct 180 ms 30968 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 7 ms 632 KB Output is correct
3 Correct 10 ms 632 KB Output is correct
4 Correct 10 ms 632 KB Output is correct
5 Correct 10 ms 632 KB Output is correct
6 Correct 6 ms 376 KB Output is correct
7 Correct 6 ms 504 KB Output is correct
8 Correct 8 ms 504 KB Output is correct
9 Correct 8 ms 632 KB Output is correct
10 Correct 190 ms 28536 KB Output is correct
11 Correct 191 ms 30696 KB Output is correct
12 Correct 223 ms 35928 KB Output is correct
13 Correct 224 ms 33760 KB Output is correct
14 Correct 7 ms 504 KB Output is correct
15 Correct 191 ms 25848 KB Output is correct
16 Correct 139 ms 20728 KB Output is correct
17 Correct 209 ms 25996 KB Output is correct
18 Correct 167 ms 29436 KB Output is correct
19 Correct 172 ms 28664 KB Output is correct
20 Correct 173 ms 30844 KB Output is correct
21 Correct 180 ms 30968 KB Output is correct
22 Correct 338 ms 15736 KB Output is correct
23 Correct 330 ms 14424 KB Output is correct
24 Correct 324 ms 15608 KB Output is correct
25 Correct 7 ms 504 KB Output is correct
26 Correct 142 ms 7416 KB Output is correct
27 Correct 266 ms 13228 KB Output is correct
28 Correct 141 ms 26232 KB Output is correct
29 Correct 182 ms 30840 KB Output is correct
30 Correct 179 ms 30760 KB Output is correct
31 Correct 7 ms 760 KB Output is correct