oj.uz

Submission #173361

# Submission time Handle Problem Language Result Execution time Memory
173361 2020-01-03T19:21:05 Z ZwariowanyMarcin Designated Cities (JOI19_designated_cities) C++14
39 / 100
 1270 ms 36692 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define ss(x) (int) x.size()
#define pb push_back
#define ll long long
#define cat(x) cerr << #x << " = " << x << endl
#define FOR(i, n) for(int i = 0; i < n; ++i)

using namespace std;	

const int nax = 2e5 + 111;

int n, nn;
int a, b, c, d;
vector <pair<int,int>> v[nax];
ll all;
ll ans[nax];

int died[nax];
int siz[nax];

void dfs(int u, int p) {
	siz[u] = 1;
	nn++;
	for(auto it : v[u]) 
		if(it.fi != p && !died[it.fi]) {
			dfs(it.fi, u);
			siz[u] += siz[it.fi];
		}
}

int daj(int u, int p) {
	for(auto it : v[u]) 
		if(it.fi != p && !died[it.fi] && nn <= 2 * siz[it.fi])
			return daj(it.fi, u);
	return u;
}

ll oblicz(int u, int p) {
	ll sum = 0;
	for(auto it : v[u]) {
		if(it.fi == p) sum += it.se;
		else if(!died[it.fi])
			sum += oblicz(it.fi, u);
	}
	return sum;
}

ll dp[nax];
	
void makedp(int u, int p) {
	dp[u] = 0;
	for(auto it : v[u])
		if(it.fi != p && !died[it.fi]) {
			makedp(it.fi, u);
			dp[u] = max(dp[u], dp[it.fi] + it.se);
		}
}

vector <pair<ll, int>> vec;

void go(int u, int p, ll cost = 0, int anc = -1) {
	tuple <ll, int, int> best = make_tuple(-1, 0, 0);
	for(auto it : v[u])
		if(it.fi != p && !died[it.fi])
			best = max(best, make_tuple(dp[it.fi] + it.se, it.fi, it.se));
	if(get<0> (best) != -1)
		go(get<1> (best), u, cost + get<2> (best), (anc == -1 ? get<1> (best) : anc));
	else
		vec.pb(mp(cost, anc));
	for(auto it : v[u])
		if(it.fi != p && !died[it.fi] && it.fi != get<1> (best))
			go(it.fi, u, it.se, (anc == -1 ? it.fi : anc));
}

ll o[nax];
	
void solve(int u) {
	ll cnt = o[u];
	makedp(u, 0);
	go(u, 0);
	sort(vec.begin(), vec.end());
	reverse(vec.begin(), vec.end());
	int h = 0;
	for(int i = 0; i < ss(vec); ++i) {
		if(vec[i].se != vec[0].se) h = 1;
		if(!h) ans[i + 2] = max(ans[i + 2], (cnt += vec[i].fi));
		else ans[i + 1] = max(ans[i + 1], (cnt += vec[i].fi));
	}
	vec.clear();
}
	
void pro(int u, int p, ll cost) {
	ll k = 0;
	for(auto it : v[u]) {
		if(it.fi != p)
			;
		else
			k = it.se;
	}
	cost -= k;
	o[u] = cost;
	ans[1] = max(ans[1], o[u]);
	for(auto it : v[u])
		if(it.fi != p)
			pro(it.fi, u, cost + it.se);
}
			

void decomp(int u) {
	nn = 0;
	dfs(u, 0);
	int c = daj(u, 0);
	solve(c);
	died[c] = 1;
	for(auto it : v[c])
		if(!died[it.fi])
			decomp(it.fi);
}
	
			
int main() {
	scanf("%d", &n);
	for(int i = 1; i < n; ++i) {
		scanf("%d %d %d %d", &a, &b, &c, &d);
		v[a].pb(mp(b, c));
		v[b].pb(mp(a, d));
		all += c + d;
	}
	
	o[1] = oblicz(1, 0);
	pro(1, 0, o[1]);
	
	decomp(1);
	
	for(int i = 1; i <= n; ++i)
		ans[i] = max(ans[i], ans[i - 1]);
	
	int q;
	scanf("%d", &q);
	while(q--) {
		scanf("%d", &a);
		printf("%lld\n", all - ans[a]);
	}
	

	return 0;
}

Compilation message

designated_cities.cpp: In function 'int main()':
designated_cities.cpp:125:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
designated_cities.cpp:127:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d %d", &a, &b, &c, &d);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:142:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
designated_cities.cpp:144:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a);
   ~~~~~^~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 6 ms 4984 KB Output is correct
5 Correct 6 ms 4984 KB Output is correct
6 Correct 6 ms 4984 KB Output is correct
7 Correct 6 ms 4984 KB Output is correct
8 Correct 6 ms 4988 KB Output is correct
9 Correct 6 ms 5112 KB Output is correct
10 Correct 6 ms 4984 KB Output is correct
11 Correct 6 ms 4984 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 863 ms 20216 KB Output is correct
3 Correct 1192 ms 36436 KB Output is correct
4 Correct 859 ms 24932 KB Output is correct
5 Correct 365 ms 26600 KB Output is correct
6 Correct 1022 ms 28008 KB Output is correct
7 Correct 322 ms 27236 KB Output is correct
8 Correct 1270 ms 36444 KB Output is correct
9 Correct 270 ms 28892 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 873 ms 20044 KB Output is correct
3 Correct 1172 ms 36600 KB Output is correct
4 Correct 817 ms 25016 KB Output is correct
5 Correct 410 ms 26544 KB Output is correct
6 Correct 996 ms 28432 KB Output is correct
7 Correct 265 ms 28324 KB Output is correct
8 Correct 1210 ms 33660 KB Output is correct
9 Correct 306 ms 28540 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 6 ms 4984 KB Output is correct
5 Correct 6 ms 4984 KB Output is correct
6 Correct 6 ms 4984 KB Output is correct
7 Correct 6 ms 4984 KB Output is correct
8 Correct 6 ms 4988 KB Output is correct
9 Correct 6 ms 5112 KB Output is correct
10 Correct 6 ms 4984 KB Output is correct
11 Correct 6 ms 4984 KB Output is correct
12 Correct 6 ms 4984 KB Output is correct
13 Correct 11 ms 5240 KB Output is correct
14 Correct 10 ms 5368 KB Output is correct
15 Incorrect 10 ms 5240 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 863 ms 20216 KB Output is correct
3 Correct 1192 ms 36436 KB Output is correct
4 Correct 859 ms 24932 KB Output is correct
5 Correct 365 ms 26600 KB Output is correct
6 Correct 1022 ms 28008 KB Output is correct
7 Correct 322 ms 27236 KB Output is correct
8 Correct 1270 ms 36444 KB Output is correct
9 Correct 270 ms 28892 KB Output is correct
10 Correct 6 ms 4984 KB Output is correct
11 Correct 873 ms 20044 KB Output is correct
12 Correct 1172 ms 36600 KB Output is correct
13 Correct 817 ms 25016 KB Output is correct
14 Correct 410 ms 26544 KB Output is correct
15 Correct 996 ms 28432 KB Output is correct
16 Correct 265 ms 28324 KB Output is correct
17 Correct 1210 ms 33660 KB Output is correct
18 Correct 306 ms 28540 KB Output is correct
19 Correct 6 ms 5116 KB Output is correct
20 Correct 864 ms 26420 KB Output is correct
21 Correct 1213 ms 36692 KB Output is correct
22 Correct 837 ms 25064 KB Output is correct
23 Correct 934 ms 26580 KB Output is correct
24 Correct 788 ms 25192 KB Output is correct
25 Correct 811 ms 26444 KB Output is correct
26 Correct 779 ms 25332 KB Output is correct
27 Correct 383 ms 26600 KB Output is correct
28 Correct 934 ms 28124 KB Output is correct
29 Correct 773 ms 26436 KB Output is correct
30 Correct 687 ms 25892 KB Output is correct
31 Correct 323 ms 27484 KB Output is correct
32 Correct 1094 ms 33920 KB Output is correct
33 Correct 258 ms 28892 KB Output is correct

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 6 ms 4984 KB Output is correct
5 Correct 6 ms 4984 KB Output is correct
6 Correct 6 ms 4984 KB Output is correct
7 Correct 6 ms 4984 KB Output is correct
8 Correct 6 ms 4988 KB Output is correct
9 Correct 6 ms 5112 KB Output is correct
10 Correct 6 ms 4984 KB Output is correct
11 Correct 6 ms 4984 KB Output is correct
12 Correct 6 ms 4984 KB Output is correct
13 Correct 863 ms 20216 KB Output is correct
14 Correct 1192 ms 36436 KB Output is correct
15 Correct 859 ms 24932 KB Output is correct
16 Correct 365 ms 26600 KB Output is correct
17 Correct 1022 ms 28008 KB Output is correct
18 Correct 322 ms 27236 KB Output is correct
19 Correct 1270 ms 36444 KB Output is correct
20 Correct 270 ms 28892 KB Output is correct
21 Correct 6 ms 4984 KB Output is correct
22 Correct 873 ms 20044 KB Output is correct
23 Correct 1172 ms 36600 KB Output is correct
24 Correct 817 ms 25016 KB Output is correct
25 Correct 410 ms 26544 KB Output is correct
26 Correct 996 ms 28432 KB Output is correct
27 Correct 265 ms 28324 KB Output is correct
28 Correct 1210 ms 33660 KB Output is correct
29 Correct 306 ms 28540 KB Output is correct
30 Correct 6 ms 4984 KB Output is correct
31 Correct 11 ms 5240 KB Output is correct
32 Correct 10 ms 5368 KB Output is correct
33 Incorrect 10 ms 5240 KB Output isn't correct
34 Halted 0 ms 0 KB -