oj.uz

Submission #127137

# Submission time Handle Problem Language Result Execution time Memory
127137 2019-07-09T00:21:44 Z wilwxk Designated Cities (JOI19_designated_cities) C++14
16 / 100
 500 ms 59152 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) {
	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, viz});
	}
}

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==viz) mprof[cur][0]=mprof[cur][1];
		melhora(viz, {mprof[cur][0].first+rpeso, cur});

		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:61:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
designated_cities.cpp:63: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:71:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
designated_cities.cpp:73: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 5112 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 316 ms 26104 KB Output is correct
3 Correct 383 ms 49100 KB Output is correct
4 Correct 300 ms 26104 KB Output is correct
5 Correct 305 ms 25904 KB Output is correct
6 Correct 334 ms 29432 KB Output is correct
7 Correct 268 ms 24864 KB Output is correct
8 Correct 397 ms 49912 KB Output is correct
9 Correct 241 ms 23960 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4988 KB Output is correct
2 Correct 325 ms 26076 KB Output is correct
3 Correct 500 ms 59152 KB Output is correct
4 Correct 325 ms 30896 KB Output is correct
5 Correct 414 ms 32256 KB Output is correct
6 Correct 435 ms 36216 KB Output is correct
7 Correct 246 ms 30272 KB Output is correct
8 Correct 400 ms 47228 KB Output is correct
9 Correct 252 ms 29976 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 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 316 ms 26104 KB Output is correct
3 Correct 383 ms 49100 KB Output is correct
4 Correct 300 ms 26104 KB Output is correct
5 Correct 305 ms 25904 KB Output is correct
6 Correct 334 ms 29432 KB Output is correct
7 Correct 268 ms 24864 KB Output is correct
8 Correct 397 ms 49912 KB Output is correct
9 Correct 241 ms 23960 KB Output is correct
10 Correct 6 ms 4988 KB Output is correct
11 Correct 325 ms 26076 KB Output is correct
12 Correct 500 ms 59152 KB Output is correct
13 Correct 325 ms 30896 KB Output is correct
14 Correct 414 ms 32256 KB Output is correct
15 Correct 435 ms 36216 KB Output is correct
16 Correct 246 ms 30272 KB Output is correct
17 Correct 400 ms 47228 KB Output is correct
18 Correct 252 ms 29976 KB Output is correct
19 Correct 7 ms 4984 KB Output is correct
20 Incorrect 340 ms 32596 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 5112 KB Output is correct
2 Incorrect 6 ms 4984 KB Output isn't correct
3 Halted 0 ms 0 KB -