Submission #319506

#	Time	Username	Problem	Language	Result	Execution time	Memory
319506		ronnith	Putovanje (COCI20_putovanje)	C++14	20 / 110	13 ms	1132 KiB

putovanje

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#warning Check Integer OverFlow
#define ll long long
#define rep(i,a,b) for(int i=a;i<b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define trav(a,b) for(auto a:b)
#define sz(a) a.size()
#define maxs(a,b) if(b>a)a=b
#define mins(a,b) if(b<a)a=b
#ifdef LOCAL 
	#define dbg(x) cerr<<"["<<#x<<":"<<x<<"] "
	#define dbg2(a,b) dbg(a);dbg(b)
	#define dbg3(a,b,c) dbg2(a,b);dbg(c)
	#define dln cerr << ln
#else
	#define dbg(x) 0
	#define dbg2(a,b) 0
	#define dbg3(a,b,c) 0
	#define dln 0
#endif
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (((a)/(__gcd(a,b))) * b)
#define print(arr) for(auto it = arr.begin();it < arr.end();it ++){cout << *it << " ";}cout << ln;
#define all(a) (a).begin(), (a).end()
#define vi vector<int>
#define v vector
#define p pair
#define pii p<int,int>
#define pb push_back
#define mk make_pair
#define f first
#define s second
#define ln "\n"
#define size siz
typedef long double ld;
using namespace std;
using namespace __gnu_pbds;
ll modF=1e9+7;

template<class T> using iset = tree<
T,
null_type,
less<T>,
rb_tree_tag,
tree_order_statistics_node_update>;

/*OUTPUT

*/

int n,timer;
vector<int> adj[2000];
int en[2000];
int pr[2000];
int size[2000];
int vis[2000];

map<int,map<int,int>> fr;
map<int,map<int,pii>> cost;

int dfs(int x,int par = -1){
	if(vis[x])return 0;
	vis[x] = 1;
	en[timer] = x;
	size[x] = 1;
	pr[x] = par;
	timer ++;
	for(auto e:adj[x]){
		size[x] += dfs(e,x);
	}
	return size[x];
}

bool fn(int i,int j){
	if(fr.find(i) == fr.end())return false;
	if(fr[i].find(j) == fr[i].end())return false;
	return true;
}

void solve(){
	cin >> n;
	rep(i,0,n - 1){
		int x,y,c1,c2;
		cin >> x >> y >> c1 >> c2;
		x --;y --;
		adj[x].pb(y);
		adj[y].pb(x);
		fr[x][y] = 0;
		cost[x][y] = mk(c1,c2);
	}
	dfs(0);
	ll ans = 0;
	for(int i = 1;i < n;i ++){
		set<int> q;
		for(int j = i;j < i + size[en[i]];j ++){
			q.insert(en[j]);
		}
		int crr = en[i];
		int prev = pr[en[i]];
		if(!fn(crr,prev)){
			swap(crr,prev);
		} 
		for(auto e:q){
			if(e != 0){
				if(q.find(e - 1) == q.end()){
					fr[crr][prev] ++;
				}
			}
			if(e != n - 1){
				if(q.find(e + 1) == q.end()){
					fr[crr][prev] ++;
				}
			}
		}
		// dbg(n);
		dbg(en[i]);
		dbg2(i,fr[crr][prev]);
		dln;
	}

	for(auto e:fr){
		for(auto ed:e.s){
			dbg2(e.f,ed.f);
			dbg2(cost[e.f][ed.f].f,cost[e.f][ed.f].s);
			dbg(fr[e.f][ed.f]);
			dln;
			if(cost[e.f][ed.f].f * fr[e.f][ed.f] < cost[e.f][ed.f].s){
				ans += cost[e.f][ed.f].f * fr[e.f][ed.f];
			}
			else{
				ans += cost[e.f][ed.f].s;
			}
		}
	}

	cout << ans << ln;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int t = 1;
	// cin >> t;
	while(t --){
		solve();
	}
}

Compilation message (stderr)

putovanje.cpp:4:2: warning: #warning Check Integer OverFlow [-Wcpp]
    4 | #warning Check Integer OverFlow
      |  ^~~~~~~
putovanje.cpp: In function 'void solve()':
putovanje.cpp:18:17: warning: statement has no effect [-Wunused-value]
   18 |  #define dbg(x) 0
      |                 ^
putovanje.cpp:118:3: note: in expansion of macro 'dbg'
  118 |   dbg(en[i]);
      |   ^~~
putovanje.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 |  #define dbg2(a,b) 0
      |                    ^
putovanje.cpp:119:3: note: in expansion of macro 'dbg2'
  119 |   dbg2(i,fr[crr][prev]);
      |   ^~~~
putovanje.cpp:21:14: warning: statement has no effect [-Wunused-value]
   21 |  #define dln 0
      |              ^
putovanje.cpp:120:3: note: in expansion of macro 'dln'
  120 |   dln;
      |   ^~~
putovanje.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 |  #define dbg2(a,b) 0
      |                    ^
putovanje.cpp:125:4: note: in expansion of macro 'dbg2'
  125 |    dbg2(e.f,ed.f);
      |    ^~~~
putovanje.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 |  #define dbg2(a,b) 0
      |                    ^
putovanje.cpp:126:4: note: in expansion of macro 'dbg2'
  126 |    dbg2(cost[e.f][ed.f].f,cost[e.f][ed.f].s);
      |    ^~~~
putovanje.cpp:18:17: warning: statement has no effect [-Wunused-value]
   18 |  #define dbg(x) 0
      |                 ^
putovanje.cpp:127:4: note: in expansion of macro 'dbg'
  127 |    dbg(fr[e.f][ed.f]);
      |    ^~~
putovanje.cpp:21:14: warning: statement has no effect [-Wunused-value]
   21 |  #define dln 0
      |              ^
putovanje.cpp:128:4: note: in expansion of macro 'dln'
  128 |    dln;
      |    ^~~

• Subtask 1: 20 / 20
• Subtask 2: 0 / 25
• Subtask 3: 0 / 65