oj.uz

Submission #127139

# Submission time Handle Problem Language Result Execution time Memory
127139 2019-07-09T00:24:35 Z wilwxk Designated Cities (JOI19_designated_cities) C++14
16 / 100
 402 ms 53068 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];
ll dp[MAXN];
ll respf[MAXN], somaf;
int n, q;

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 predfs(int cur, int p) {
	mprof[cur][0].second=cur;
	for(auto aresta : g[cur]) {
		int viz; ll peso, rpeso;
		tie(viz, peso, rpeso)=aresta;
		if(viz==p) continue;
		predfs(viz, cur);

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

void dfs(int cur, int p) {
	respf[1]=max(respf[1], dp[cur]);
	respf[2]=max(respf[2], dp[cur]+mprof[cur][0].first);
	// 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;
	}
}

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;
	}

	predfs(1, 1);
	dfs(1, 1);

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

Compilation message

designated_cities.cpp: In function 'int main()':
designated_cities.cpp:62:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
designated_cities.cpp:64: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:72:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
designated_cities.cpp:74: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
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5116 KB Output is correct
2 Incorrect 6 ms 4984 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 6 ms 4984 KB Output is correct
2 Correct 336 ms 25928 KB Output is correct
3 Correct 402 ms 49016 KB Output is correct
4 Correct 324 ms 26116 KB Output is correct
5 Correct 324 ms 25708 KB Output is correct
6 Correct 373 ms 29444 KB Output is correct
7 Correct 275 ms 24740 KB Output is correct
8 Correct 391 ms 49816 KB Output is correct
9 Correct 224 ms 23960 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 338 ms 25956 KB Output is correct
3 Correct 400 ms 53068 KB Output is correct
4 Correct 277 ms 26232 KB Output is correct
5 Correct 304 ms 26024 KB Output is correct
6 Correct 370 ms 30164 KB Output is correct
7 Correct 240 ms 24220 KB Output is correct
8 Correct 368 ms 41208 KB Output is correct
9 Correct 209 ms 24216 KB Output is correct

Subtask #4
0 / 17.0

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

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 336 ms 25928 KB Output is correct
3 Correct 402 ms 49016 KB Output is correct
4 Correct 324 ms 26116 KB Output is correct
5 Correct 324 ms 25708 KB Output is correct
6 Correct 373 ms 29444 KB Output is correct
7 Correct 275 ms 24740 KB Output is correct
8 Correct 391 ms 49816 KB Output is correct
9 Correct 224 ms 23960 KB Output is correct
10 Correct 6 ms 4984 KB Output is correct
11 Correct 338 ms 25956 KB Output is correct
12 Correct 400 ms 53068 KB Output is correct
13 Correct 277 ms 26232 KB Output is correct
14 Correct 304 ms 26024 KB Output is correct
15 Correct 370 ms 30164 KB Output is correct
16 Correct 240 ms 24220 KB Output is correct
17 Correct 368 ms 41208 KB Output is correct
18 Correct 209 ms 24216 KB Output is correct
19 Correct 6 ms 5116 KB Output is correct
20 Incorrect 327 ms 26228 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

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