oj.uz

Submission #105111

# Submission time Handle Problem Language Result Execution time Memory
105111 2019-04-10T14:58:08 Z Just_Solve_The_Problem Designated Cities (JOI19_designated_cities) C++11
7 / 100
 438 ms 39688 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 (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:76:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
designated_cities.cpp: In function 'int main()':
designated_cities.cpp:77:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
designated_cities.cpp:84: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:101: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: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 Incorrect 7 ms 4992 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4992 KB Output is correct
2 Correct 406 ms 22068 KB Output is correct
3 Correct 438 ms 39252 KB Output is correct
4 Correct 342 ms 22024 KB Output is correct
5 Correct 378 ms 21656 KB Output is correct
6 Correct 426 ms 24780 KB Output is correct
7 Correct 344 ms 21700 KB Output is correct
8 Correct 382 ms 39688 KB Output is correct
9 Correct 215 ms 20652 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 5120 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4992 KB Output is correct
2 Correct 406 ms 22068 KB Output is correct
3 Correct 438 ms 39252 KB Output is correct
4 Correct 342 ms 22024 KB Output is correct
5 Correct 378 ms 21656 KB Output is correct
6 Correct 426 ms 24780 KB Output is correct
7 Correct 344 ms 21700 KB Output is correct
8 Correct 382 ms 39688 KB Output is correct
9 Correct 215 ms 20652 KB Output is correct
10 Incorrect 6 ms 5120 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

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