Submission #319515

#	Time	Username	Problem	Language	Result	Execution time	Memory
319515		ronnith	Putovanje (COCI20_putovanje)	C++14	45 / 110	1084 ms	53476 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[200000];
int en[200000];
int pr[200000];
int size[200000];
int vis[200000];
int ind[200000];

map<ll,map<ll,ll>> fr;
map<ll,map<ll,p<ll,ll>>> 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);
		ind[x] ++;
		ind[y] ++;
	}
	bool pos =  true;
	int i1;
	rep(i,0,n){
		if(ind[i] > 2){
			pos = false;
		}
		if(ind[i] == 1){
			i1 = i;
		}
	}

	ll ans = 0;
	if(pos){
		dfs(i1);
		dbg(i1);
		// int ans = 0;
		dbg("YES");
		set<int> q;
		int run = 0;
		for(int i = 0;i < n;i ++){
			dbg(en[i]);
			// dln;
			if(en[i] != n - 1){
				if(q.find(en[i] + 1) == q.end()){
					run ++;
				}
				else{
					run --;
				}
			}
			if(en[i] != 0){
				if(q.find(en[i] - 1) == q.end()){
					run ++;
				}
				else{
					run --;
				}
			}
			dbg(run);
			dln;
			if(i != n - 1){
				int crr = en[i];
				int prev = en[i + 1];
				if(!fn(crr,prev)){
					swap(crr,prev);
				}
				fr[crr][prev] = run;
			}
			q.insert(en[i]);
		}
	}
	else{
		dfs(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:110:3: note: in expansion of macro 'dbg'
  110 |   dbg(i1);
      |   ^~~
putovanje.cpp:18:17: warning: statement has no effect [-Wunused-value]
   18 |  #define dbg(x) 0
      |                 ^
putovanje.cpp:112:3: note: in expansion of macro 'dbg'
  112 |   dbg("YES");
      |   ^~~
putovanje.cpp:18:17: warning: statement has no effect [-Wunused-value]
   18 |  #define dbg(x) 0
      |                 ^
putovanje.cpp:116:4: note: in expansion of macro 'dbg'
  116 |    dbg(en[i]);
      |    ^~~
putovanje.cpp:18:17: warning: statement has no effect [-Wunused-value]
   18 |  #define dbg(x) 0
      |                 ^
putovanje.cpp:134:4: note: in expansion of macro 'dbg'
  134 |    dbg(run);
      |    ^~~
putovanje.cpp:21:14: warning: statement has no effect [-Wunused-value]
   21 |  #define dln 0
      |              ^
putovanje.cpp:135:4: note: in expansion of macro 'dln'
  135 |    dln;
      |    ^~~
putovanje.cpp:18:17: warning: statement has no effect [-Wunused-value]
   18 |  #define dbg(x) 0
      |                 ^
putovanje.cpp:172:4: note: in expansion of macro 'dbg'
  172 |    dbg(en[i]);
      |    ^~~
putovanje.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 |  #define dbg2(a,b) 0
      |                    ^
putovanje.cpp:173:4: note: in expansion of macro 'dbg2'
  173 |    dbg2(i,fr[crr][prev]);
      |    ^~~~
putovanje.cpp:21:14: warning: statement has no effect [-Wunused-value]
   21 |  #define dln 0
      |              ^
putovanje.cpp:174:4: note: in expansion of macro 'dln'
  174 |    dln;
      |    ^~~
putovanje.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 |  #define dbg2(a,b) 0
      |                    ^
putovanje.cpp:180:4: note: in expansion of macro 'dbg2'
  180 |    dbg2(e.f,ed.f);
      |    ^~~~
putovanje.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 |  #define dbg2(a,b) 0
      |                    ^
putovanje.cpp:181:4: note: in expansion of macro 'dbg2'
  181 |    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:182:4: note: in expansion of macro 'dbg'
  182 |    dbg(fr[e.f][ed.f]);
      |    ^~~
putovanje.cpp:21:14: warning: statement has no effect [-Wunused-value]
   21 |  #define dln 0
      |              ^
putovanje.cpp:183:4: note: in expansion of macro 'dln'
  183 |    dln;
      |    ^~~
putovanje.cpp:65:10: warning: 'i1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   65 |  if(vis[x])return 0;
      |     ~~~~~^
putovanje.cpp:97:6: note: 'i1' was declared here
   97 |  int i1;
      |      ^~

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