Submission #132860

#	Time	Username	Problem	Language	Result	Execution time	Memory
132860		ekrem	Designated Cities (JOI19_designated_cities)	C++98	16 / 100	858 ms	92536 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 10000000000000007
#define inf 10000000000000007
#define N 1000005
using namespace std;

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

ll n, zu, ans, bir, iki, top, say[N], a[N], x[N], bas[N], son[N], par[N], cvp[N], h[N], lazy[4*N];
ii dp[N], seg[4*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 of(ll node, ll par, ll us){
	ll top = us + say[node];
	cvp[1] = max(cvp[1], top);
	ii mx = mp(0, node), mx2 = mp(0, node);
	for(ll i = 0; i < g[node].size(); i++)
		if(coc != par){
			of(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);
}

bool bak(ll node, ll pr, ll ara){
	if(node == ara){
		h[node] = 1;
		return 1;
	}
	bool don = 0;
	for(ll i = 0; i < g[node].size(); i++){
		if(pr == coc)
			continue;
		don |= bak(coc, node, ara);
	}
	if(don)
		h[node] = 1;
	return don;
}

void dfs(ll node, ll pr, ll us){
	bas[node] = ++zu;
	if(h[node])
		us = 0;
	x[zu] = node;
	for(ll i = 0; i < g[node].size(); i++){
		if(coc == pr)
			continue;
		par[coc] = node;
		dfs(coc, node, us + yol);
	}
	a[bas[node]] = us;
	son[node] = zu;
}

void bu(ll k, ll bas, ll son){
	if(bas == son){
		seg[k] = mp(a[bas], bas);
		return;
	}
	bu(sol, bas, orta);
	bu(sag, orta + 1, son);
	seg[k] = max(seg[sol], seg[sag]);
}

void put(ll k, ll bas, ll son, ll z){
	seg[k].st += z;
	lazy[k] += z;
}

void push(ll k, ll bas, ll son){
	put(sol, bas, orta, lazy[k]);
	put(sag, orta + 1, son, lazy[k]);
	lazy[k] = 0;
}

void up(ll k, ll bas, ll son, ll x, ll y, ll z){
	if(bas > y or son < x)
		return;
	if(bas >= x and son <= y){
		put(k, bas, son, z);
		return;
	}
	push(k, bas, son);
	up(sol, bas, orta, x, y, z);
	up(sag, orta + 1, son, x, y, z);
	seg[k] = max(seg[sol], seg[sag]);
}

ii qu(ll k, ll bas, ll son, ll x, ll y){
	if(bas > y or son < x)
		return mp(0, 0);
	if(bas >= x and son <= y)
		return seg[k];
	push(k, bas, son);
	return max(qu(sol, bas, orta, x, y), qu(sag, orta + 1, son, x, y));
}

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);
	of(1, 0, 0);
	// cout << bir << " " << iki << " " << ans << " " << top << endl;
	// printf("%lld\n", top - ans);
	cvp[2] = top - ans;
	cvp[1] = top - cvp[1];
	bak(bir, 0, iki);
	dfs(bir, 0, 0);
	bu(1, 1, n);
	// for(ll i = 1; i <= n; i++)cout << h[i] << " ";cout << endl;
	// for(ll i = 1; i <= n; i++)cout << x[i] << " ";cout << endl;
	// for(ll i = 1; i <= n; i++)cout << x[i] << " -> "<< a[i] << "\n";cout << endl;
	for(ll i = 3; i <= n; i++){
		ii of = qu(1, 1, n, 1, n);
		ans += of.st;
		cvp[i] = top - ans;
		up(1, 1, n, of.nd, of.nd, -inf);
		// cout << of.nd << " " << x[of.nd] << endl;
		ll node = par[x[of.nd]];
		while(1){
			// cout << node << " " << a[bas[node]] << " -> " << par[node] << endl;
			if(h[node] or !node)
				break;
			up(1, 1, n, bas[node], son[node], -a[bas[node]]);
			h[node] = 1;
			node = par[node];
		}
	}
	ll q;
	scanf("%lld",&q);
	while(q--){
		ll x;
		scanf("%lld",&x);
		printf("%lld\n", cvp[x]);
	}
	// for(ll i = 1; i <= n; i++)
	// 	cout << i << " " << cvp[i] << endl;
	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 of(ll, ll, ll)':
designated_cities.cpp:37: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 'bool bak(ll, ll, ll)':
designated_cities.cpp:63: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:78: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:134:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&n);
  ~~~~~^~~~~~~~~~~
designated_cities.cpp:137: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);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:171:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&q);
  ~~~~~^~~~~~~~~~~
designated_cities.cpp:174:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&x);
   ~~~~~^~~~~~~~~~~

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