oj.uz

Submission #105113

# Submission time Handle Problem Language Result Execution time Memory
105113 2019-04-10T15:00:25 Z Just_Solve_The_Problem Designated Cities (JOI19_designated_cities) C++11
16 / 100
 534 ms 45940 KB 
#include <bits/stdc++.h>

#define fr first
#define sc second
#define ll long long

using namespace std;

const int N = (int)2e5 + 7;

vector<pair<int, int>> gr[N];
int n;
ll ans[N];
ll h[N];
pair < ll, int > dp[N];
int tin[N], tout[N], used[N], par[N];
int tiktak;

void precalc(int v, int pr) {
	tin[v] = ++tiktak;
	par[v] = pr;
	for (auto tto : gr[v]) {
		int to = tto.fr;
		int w = tto.sc;
		if (to == pr) {
			continue;
		}
		h[v] += w;
		precalc(to, v);
		h[v] += h[to];
	}
	tout[v] = tiktak;
}

pair < int, int > ans2;

void dfs1(int v, int pr, ll H = 0) {
	ll res = 0;
	for (auto tto : gr[v]) {
		int to = tto.fr;
		int w = tto.sc;
		if (to == pr) {
			H += w;
		}
	}
	ans[1] = min(ans[1], H + h[v]);
	dp[v] = {h[v], v};
	ll mx = 1e18;
	int ind = -1;
	for (auto tto : gr[v]) {
		int to = tto.fr;
		int w = tto.sc;
		if (to == pr) continue;
		dfs1(to, v, H + h[v] - h[to] - w);
		if (mx != 1e18) {
			if (mx + dp[to].fr + h[v] - w - h[to] + H < ans[2]) {
				// cout << mx + dp[to].fr + h[v] - w - h[to] + H << ' ' << dp[ind].sc << ' ' << dp[to].sc << '\n';
				ans[2] = mx + dp[to].fr + h[v] - w - h[to] + H;
				ans2 = {dp[ind].sc, dp[to].sc};
			}
		} 
		if (dp[to].fr - w - h[to] < mx) {
			mx = dp[to].fr - w - h[to];
			ind = to;
		}
		if (dp[to].fr + H + h[v] - h[to] - w < ans[2]) {
			ans[2] = dp[to].fr + H + h[v] - h[to] - w;
			ans2 = {v, dp[to].sc};
		}
		if (make_pair(dp[to].fr + h[v] - w - h[to], dp[to].sc) < dp[v]) {
			dp[v] = make_pair(dp[to].fr + h[v] - w - h[to], dp[to].sc);
		}
	}
}

bool upper(int a, int b) {
	return tin[a] <= tin[b] && tout[a] >= tout[b];
}

main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		ans[i] = 1e18;
		dp[i] = {1e18, 0};
	}
	for (int i = 1; i < n; i++) {
		int a, b, c, d;
		scanf("%d %d %d %d", &a, &b, &c, &d);
		gr[a].push_back({b, c});
		gr[b].push_back({a, d});
	}
	precalc(1, 1);
	dfs1(1, 1);
	used[ans2.fr] = 1;
	while (!upper(ans2.fr, ans2.sc)) {
		ans2.fr = par[ans2.fr];
		used[ans2.fr] = 1;
	}
	used[ans2.sc] = 1;
	while (!upper(ans2.sc, ans2.fr)) {
		ans2.sc = par[ans2.sc];
		used[ans2.sc] = 1;
	}
	int q;
	scanf("%d", &q);
	while (q--) {
		int x;
		scanf("%d", &x);
		printf("%lld\n", ans[x]);
	}
}

Compilation message

designated_cities.cpp: In function 'void dfs1(int, int, long long int)':
designated_cities.cpp:38:5: warning: unused variable 'res' [-Wunused-variable]
  ll res = 0;
     ^~~
designated_cities.cpp: At global scope:
designated_cities.cpp:80:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
designated_cities.cpp: In function 'int main()':
designated_cities.cpp:81:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
designated_cities.cpp:88: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:105:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
designated_cities.cpp:108:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
   ~~~~~^~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Incorrect 8 ms 4992 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 7 ms 4992 KB Output is correct
2 Correct 421 ms 21956 KB Output is correct
3 Correct 469 ms 38656 KB Output is correct
4 Correct 388 ms 21756 KB Output is correct
5 Correct 434 ms 21160 KB Output is correct
6 Correct 423 ms 24320 KB Output is correct
7 Correct 392 ms 21224 KB Output is correct
8 Correct 534 ms 39280 KB Output is correct
9 Correct 343 ms 20196 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4992 KB Output is correct
2 Correct 435 ms 26104 KB Output is correct
3 Correct 514 ms 45940 KB Output is correct
4 Correct 430 ms 24852 KB Output is correct
5 Correct 490 ms 25584 KB Output is correct
6 Correct 461 ms 28896 KB Output is correct
7 Correct 301 ms 25796 KB Output is correct
8 Correct 445 ms 37240 KB Output is correct
9 Correct 318 ms 24632 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Incorrect 8 ms 4992 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB Output is correct
2 Correct 421 ms 21956 KB Output is correct
3 Correct 469 ms 38656 KB Output is correct
4 Correct 388 ms 21756 KB Output is correct
5 Correct 434 ms 21160 KB Output is correct
6 Correct 423 ms 24320 KB Output is correct
7 Correct 392 ms 21224 KB Output is correct
8 Correct 534 ms 39280 KB Output is correct
9 Correct 343 ms 20196 KB Output is correct
10 Correct 8 ms 4992 KB Output is correct
11 Correct 435 ms 26104 KB Output is correct
12 Correct 514 ms 45940 KB Output is correct
13 Correct 430 ms 24852 KB Output is correct
14 Correct 490 ms 25584 KB Output is correct
15 Correct 461 ms 28896 KB Output is correct
16 Correct 301 ms 25796 KB Output is correct
17 Correct 445 ms 37240 KB Output is correct
18 Correct 318 ms 24632 KB Output is correct
19 Correct 6 ms 4992 KB Output is correct
20 Incorrect 424 ms 26184 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Incorrect 8 ms 4992 KB Output isn't correct
3 Halted 0 ms 0 KB -