Submission #105113

#	Time	Username	Problem	Language	Result	Execution time	Memory
105113		Just_Solve_The_Problem	Designated Cities (JOI19_designated_cities)	C++11	16 / 100	534 ms	45940 KiB

designated_cities

#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 (stderr)

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
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 0 / 17
• Subtask 5: 0 / 17
• Subtask 6: 0 / 44