Submission #201444

#	Time	Username	Problem	Language	Result	Execution time	Memory
201444		ami	Putovanje (COCI20_putovanje)	C++17	110 / 110	338 ms	35928 KiB

putovanje

#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 / 20
• Subtask 2: 25 / 25
• Subtask 3: 65 / 65