Submission #132854

#	Time	Username	Problem	Language	Result	Execution time	Memory
132854		ekrem	Designated Cities (JOI19_designated_cities)	C++98	9 / 100	467 ms	74164 KiB

designated_cities

#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define sol (k+k)
#define sag (k+k+1)
#define orta ((bas+son)/2)
#define coc g[node][i].st
#define yol g[node][i].nd.st
#define tyol g[node][i].nd.nd
#define mod 1000000007
#define inf 1000000009
#define N 1000005
using namespace std;

typedef long long ll;
typedef pair < ll , ll > ii;
typedef pair < ll , ii > iii;

ll n, ans, bir, iki, top, say[N];
ii dp[N];
vector < iii > g[N];

void hazirla(ll node, ll par){
	for(ll i = 0; i < g[node].size(); i++)
		if(coc != par){
			hazirla(coc, node);
			say[node] += say[coc] + tyol;
		}
}

void dfs(ll node, ll par, ll us){
	ll top = us + say[node];
	ii mx = mp(0, node), mx2 = mp(0, node);
	for(ll i = 0; i < g[node].size(); i++)
		if(coc != par){
			dfs(coc, node, us + say[node] - (say[coc] + tyol) + yol);
			mx2 = max(mx2, mp(-say[coc] - tyol + tyol + yol + dp[coc].st, dp[coc].nd) );
			if(mx2 > mx)
				swap(mx, mx2);
		}
	if(top + mx.st + mx2.st > ans){
		ans = top + mx.st + mx2.st;
		bir = mx.nd;
		iki = mx2.nd;
	}
	if(say[node] + mx.st > ans){
		ans = say[node] + mx.st;
		bir = mx.nd;
		iki = node;
	}
	dp[node] = mp(say[node] + mx.st, mx.nd);
	// cout << node << " " << say[node] << " " << top << " " << dp[node].st << " " << dp[node].nd << endl;
}


int main() {
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
	scanf("%lld",&n);
	for(ll i = 1; i < n; i++){
		ll a, b, c, d;
		scanf("%lld %lld %lld %lld",&a ,&b ,&c ,&d);
		top += c + d;
		g[a].pb(mp(b, mp(c, d)));
		g[b].pb(mp(a, mp(d, c)));
	}
	hazirla(1, 0);
	dfs(1, 0, 0);
	// cout << bir << " " << iki << " " << ans << endl;
	printf("%lld\n", top - ans);
	return 0;
}

Compilation message (stderr)

designated_cities.cpp: In function 'void hazirla(ll, ll)':
designated_cities.cpp:26:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ll i = 0; i < g[node].size(); i++)
                ~~^~~~~~~~~~~~~~~~
designated_cities.cpp: In function 'void dfs(ll, ll, ll)':
designated_cities.cpp:36:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ll i = 0; i < g[node].size(); i++)
                ~~^~~~~~~~~~~~~~~~
designated_cities.cpp: In function 'int main()':
designated_cities.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&n);
  ~~~~~^~~~~~~~~~~
designated_cities.cpp:64:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld %lld %lld",&a ,&b ,&c ,&d);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 6
• Subtask 2: 0 / 7
• Subtask 3: 9 / 9
• Subtask 4: 0 / 17
• Subtask 5: 0 / 17
• Subtask 6: 0 / 44