oj.uz

Submission #127154

# Submission time Handle Problem Language Result Execution time Memory
127154 2019-07-09T01:28:04 Z wilwxk Designated Cities (JOI19_designated_cities) C++14
39 / 100
 2000 ms 56568 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN=2e5+5;
vector<tuple<int, ll, ll> > g[MAXN];
pair<ll, int> mprof[MAXN][2];
bool marc[MAXN];
ll dp[MAXN];
ll respf[MAXN], somaf;
int n, q, raiz;

void melhora(int cur, pair<ll, int> val) {
	if(val.first>=mprof[cur][0].first) {
		mprof[cur][1]=mprof[cur][0];
		mprof[cur][0]=val;
	}
	else if(val.first>mprof[cur][1].first) {
		mprof[cur][1]=val;
	}
}

void recalc(int cur, int p) {
	dp[cur]=0;
	mprof[cur][0]=mprof[cur][1]={0, cur};
	for(auto aresta : g[cur]) {
		int viz; ll peso, rpeso;
		tie(viz, peso, rpeso)=aresta;
		if(viz==p) continue;
		recalc(viz, cur);

		dp[cur]+=dp[viz]+rpeso;
		if(!marc[viz]) melhora(cur, {mprof[viz][0].first+peso, mprof[viz][0].second});
		else melhora(cur, {mprof[viz][0].first, mprof[viz][0].second});
	}
}

void dfs(int cur, int p) {
	respf[1]=max(respf[1], dp[cur]);
	if(dp[cur]+mprof[cur][0].first>respf[2]) {
		respf[2]=dp[cur]+mprof[cur][0].first;
		raiz=cur;
	}
	// printf("dp[%d]= %lld // mprof[%d][0]= %lld, %d\n", cur, dp[cur], cur, mprof[cur][0].first, mprof[cur][0].second);
	for(auto aresta : g[cur]) {
		int viz; ll peso, rpeso;
		tie(viz, peso, rpeso)=aresta;
		if(viz==p) continue;

		ll dpc=dp[cur], dpv=dp[viz];
		auto mprofc0=mprof[cur][0], mprofc1=mprof[cur][1];
		auto mprofv0=mprof[viz][0], mprofv1=mprof[viz][1];

		dp[cur]-=(dp[viz]+rpeso);
		dp[viz]+=(dp[cur]+peso);
		if(mprof[cur][0].second==mprof[viz][0].second) mprof[cur][0]=mprof[cur][1];
		melhora(viz, {mprof[cur][0].first+rpeso, mprof[cur][0].second});

		dfs(viz, cur);

		dp[cur]=dpc; dp[viz]=dpv;
		mprof[cur][0]=mprofc0; mprof[cur][1]=mprofc1;
		mprof[viz][0]=mprofv0; mprof[viz][1]=mprofv1;
	}
}

void pinta(int cur, int p, int alvo) {
	if(cur==alvo) marc[cur]=1;
	for(auto aresta : g[cur]) {
		int viz; ll peso, rpeso;
		tie(viz, peso, rpeso)=aresta;
		if(viz==p) continue;
		pinta(viz, cur, alvo);
		if(marc[viz]) marc[cur]=1;
	}
}

ll responde(int val) {
	if(respf[val]!=0) return respf[val];
	respf[val]=responde(val-1);
	respf[val]+=mprof[raiz][0].first;
	int cara=mprof[raiz][0].second;
	pinta(raiz, raiz, cara);
	recalc(raiz, raiz);
	return respf[val];
}

int main() {
	scanf("%d", &n);
	for(int i=1; i<n; i++) {
		int a, b, c, d; scanf("%d %d %d %d", &a, &b, &c, &d);
		g[a].push_back({b, c, d}); g[b].push_back({a, d, c});
		somaf+=c; somaf+=d;
	}

	recalc(1, 1);
	dfs(1, 1);
	recalc(raiz, raiz);
	pinta(raiz, raiz, mprof[raiz][0].second);
	recalc(raiz, raiz);

	scanf("%d", &q);
	while(q--) {
		int val; scanf("%d", &val);
		printf("%lld\n", somaf-responde(val));
	}
}

Compilation message

designated_cities.cpp: In function 'int main()':
designated_cities.cpp:89:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
designated_cities.cpp:91:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a, b, c, d; scanf("%d %d %d %d", &a, &b, &c, &d);
                   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:102:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
designated_cities.cpp:104:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int val; scanf("%d", &val);
            ~~~~~^~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 6 ms 4984 KB Output is correct
4 Correct 7 ms 5112 KB Output is correct
5 Correct 6 ms 5112 KB Output is correct
6 Correct 6 ms 5036 KB Output is correct
7 Correct 6 ms 4984 KB Output is correct
8 Correct 6 ms 4984 KB Output is correct
9 Correct 7 ms 5112 KB Output is correct
10 Correct 6 ms 5112 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 5112 KB Output is correct
2 Correct 430 ms 26168 KB Output is correct
3 Correct 556 ms 54740 KB Output is correct
4 Correct 376 ms 31096 KB Output is correct
5 Correct 386 ms 31404 KB Output is correct
6 Correct 432 ms 35108 KB Output is correct
7 Correct 336 ms 30368 KB Output is correct
8 Correct 546 ms 55544 KB Output is correct
9 Correct 254 ms 29464 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 428 ms 26152 KB Output is correct
3 Correct 552 ms 56568 KB Output is correct
4 Correct 407 ms 29560 KB Output is correct
5 Correct 394 ms 29688 KB Output is correct
6 Correct 445 ms 33716 KB Output is correct
7 Correct 276 ms 27672 KB Output is correct
8 Correct 502 ms 44676 KB Output is correct
9 Correct 243 ms 27416 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 6 ms 4984 KB Output is correct
4 Correct 7 ms 5112 KB Output is correct
5 Correct 6 ms 5112 KB Output is correct
6 Correct 6 ms 5036 KB Output is correct
7 Correct 6 ms 4984 KB Output is correct
8 Correct 6 ms 4984 KB Output is correct
9 Correct 7 ms 5112 KB Output is correct
10 Correct 6 ms 5112 KB Output is correct
11 Correct 6 ms 4984 KB Output is correct
12 Correct 6 ms 4984 KB Output is correct
13 Correct 238 ms 5500 KB Output is correct
14 Correct 323 ms 5496 KB Output is correct
15 Correct 250 ms 5368 KB Output is correct
16 Correct 258 ms 5496 KB Output is correct
17 Correct 249 ms 5368 KB Output is correct
18 Correct 243 ms 5380 KB Output is correct
19 Correct 247 ms 5368 KB Output is correct
20 Correct 223 ms 5368 KB Output is correct
21 Correct 247 ms 5508 KB Output is correct
22 Correct 241 ms 5500 KB Output is correct
23 Correct 213 ms 5368 KB Output is correct
24 Correct 116 ms 5372 KB Output is correct
25 Correct 322 ms 5612 KB Output is correct
26 Correct 110 ms 5368 KB Output is correct

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 430 ms 26168 KB Output is correct
3 Correct 556 ms 54740 KB Output is correct
4 Correct 376 ms 31096 KB Output is correct
5 Correct 386 ms 31404 KB Output is correct
6 Correct 432 ms 35108 KB Output is correct
7 Correct 336 ms 30368 KB Output is correct
8 Correct 546 ms 55544 KB Output is correct
9 Correct 254 ms 29464 KB Output is correct
10 Correct 6 ms 4984 KB Output is correct
11 Correct 428 ms 26152 KB Output is correct
12 Correct 552 ms 56568 KB Output is correct
13 Correct 407 ms 29560 KB Output is correct
14 Correct 394 ms 29688 KB Output is correct
15 Correct 445 ms 33716 KB Output is correct
16 Correct 276 ms 27672 KB Output is correct
17 Correct 502 ms 44676 KB Output is correct
18 Correct 243 ms 27416 KB Output is correct
19 Correct 6 ms 5112 KB Output is correct
20 Execution timed out 2053 ms 30712 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 6 ms 4984 KB Output is correct
4 Correct 7 ms 5112 KB Output is correct
5 Correct 6 ms 5112 KB Output is correct
6 Correct 6 ms 5036 KB Output is correct
7 Correct 6 ms 4984 KB Output is correct
8 Correct 6 ms 4984 KB Output is correct
9 Correct 7 ms 5112 KB Output is correct
10 Correct 6 ms 5112 KB Output is correct
11 Correct 6 ms 4984 KB Output is correct
12 Correct 6 ms 5112 KB Output is correct
13 Correct 430 ms 26168 KB Output is correct
14 Correct 556 ms 54740 KB Output is correct
15 Correct 376 ms 31096 KB Output is correct
16 Correct 386 ms 31404 KB Output is correct
17 Correct 432 ms 35108 KB Output is correct
18 Correct 336 ms 30368 KB Output is correct
19 Correct 546 ms 55544 KB Output is correct
20 Correct 254 ms 29464 KB Output is correct
21 Correct 6 ms 4984 KB Output is correct
22 Correct 428 ms 26152 KB Output is correct
23 Correct 552 ms 56568 KB Output is correct
24 Correct 407 ms 29560 KB Output is correct
25 Correct 394 ms 29688 KB Output is correct
26 Correct 445 ms 33716 KB Output is correct
27 Correct 276 ms 27672 KB Output is correct
28 Correct 502 ms 44676 KB Output is correct
29 Correct 243 ms 27416 KB Output is correct
30 Correct 6 ms 4984 KB Output is correct
31 Correct 238 ms 5500 KB Output is correct
32 Correct 323 ms 5496 KB Output is correct
33 Correct 250 ms 5368 KB Output is correct
34 Correct 258 ms 5496 KB Output is correct
35 Correct 249 ms 5368 KB Output is correct
36 Correct 243 ms 5380 KB Output is correct
37 Correct 247 ms 5368 KB Output is correct
38 Correct 223 ms 5368 KB Output is correct
39 Correct 247 ms 5508 KB Output is correct
40 Correct 241 ms 5500 KB Output is correct
41 Correct 213 ms 5368 KB Output is correct
42 Correct 116 ms 5372 KB Output is correct
43 Correct 322 ms 5612 KB Output is correct
44 Correct 110 ms 5368 KB Output is correct
45 Correct 6 ms 5112 KB Output is correct
46 Execution timed out 2053 ms 30712 KB Time limit exceeded
47 Halted 0 ms 0 KB -