oj.uz

Submission #132859

# Submission time Handle Problem Language Result Execution time Memory
132859 2019-07-19T19:47:52 Z ekrem Designated Cities (JOI19_designated_cities) C++
16 / 100
 464 ms 71800 KB 
#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;
	// 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 << bas[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);
	// 	ll node = par[x[of.nd]];
	// 	while(1){
	// 		if(h[node] or !node)
	// 			break;
	// 		up(1, 1, n, bas[node], son[node], -a[bas[node]]);
	// 		node = par[node];
	// 	}
	// }
	cvp[1] = top - cvp[1];
	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

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:167:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&q);
  ~~~~~^~~~~~~~~~~
designated_cities.cpp:170: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.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23800 KB Output is correct
2 Incorrect 23 ms 23800 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23800 KB Output is correct
2 Correct 396 ms 41668 KB Output is correct
3 Correct 399 ms 71128 KB Output is correct
4 Correct 316 ms 46652 KB Output is correct
5 Correct 317 ms 47808 KB Output is correct
6 Correct 347 ms 51448 KB Output is correct
7 Correct 279 ms 46956 KB Output is correct
8 Correct 398 ms 71800 KB Output is correct
9 Correct 221 ms 44440 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23800 KB Output is correct
2 Correct 328 ms 41684 KB Output is correct
3 Correct 464 ms 70136 KB Output is correct
4 Correct 308 ms 42564 KB Output is correct
5 Correct 316 ms 43072 KB Output is correct
6 Correct 342 ms 47096 KB Output is correct
7 Correct 238 ms 41240 KB Output is correct
8 Correct 377 ms 58172 KB Output is correct
9 Correct 222 ms 39200 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23800 KB Output is correct
2 Incorrect 23 ms 23800 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23800 KB Output is correct
2 Correct 396 ms 41668 KB Output is correct
3 Correct 399 ms 71128 KB Output is correct
4 Correct 316 ms 46652 KB Output is correct
5 Correct 317 ms 47808 KB Output is correct
6 Correct 347 ms 51448 KB Output is correct
7 Correct 279 ms 46956 KB Output is correct
8 Correct 398 ms 71800 KB Output is correct
9 Correct 221 ms 44440 KB Output is correct
10 Correct 23 ms 23800 KB Output is correct
11 Correct 328 ms 41684 KB Output is correct
12 Correct 464 ms 70136 KB Output is correct
13 Correct 308 ms 42564 KB Output is correct
14 Correct 316 ms 43072 KB Output is correct
15 Correct 342 ms 47096 KB Output is correct
16 Correct 238 ms 41240 KB Output is correct
17 Correct 377 ms 58172 KB Output is correct
18 Correct 222 ms 39200 KB Output is correct
19 Correct 23 ms 23800 KB Output is correct
20 Incorrect 335 ms 48212 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23800 KB Output is correct
2 Incorrect 23 ms 23800 KB Output isn't correct
3 Halted 0 ms 0 KB -