Submission #376154

#	Time	Username	Problem	Language	Result	Execution time	Memory
376154		casperwang	Designated Cities (JOI19_designated_cities)	C++14	7 / 100	355 ms	30024 KiB

designated_cities

#include <bits/stdc++.h>
#define int long long
#define pb emplace_back
using namespace std;
#define debug(args...) kout("[ " + string(#args) + " ]", args)
void kout() { cerr << endl; }
template <class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ',kout(b...); }
template <class T> void pary(T L, T R) { while (L != R) cerr << *L << " \n"[++L==R]; }

struct Edge {
	int to, val;
	Edge(int t, int v) {
		to = t, val = v;
	}
};

const int MAXN = 200000;
const int INF = 1e18;
int N, Q;
int a, b, c, d;
vector <int> path[MAXN+1];
vector <Edge> E;
int ans[MAXN+1];
int cal;

void dfs_dis(int now, int par) {
	for (int id : path[now]) {
		Edge e = E[id];
		if (e.to == par) continue;
		cal += e.val;
		dfs_dis(e.to, now);
	}
}

void dfs_1(int now, int par) {
	ans[1] = min(ans[1], cal);
	for (int id : path[now]) {
		Edge e = E[id], re = E[id^1];
		if (e.to == par) continue;
		cal += re.val - e.val;
		dfs_1(e.to, now);
		cal -= re.val - e.val;
	}
}

void solve() {
	cal = 0;
	dfs_dis(1, 0);
	dfs_1(1, 0);
}

signed main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> N;
	for (int i = 1; i < N; i++) {
		cin >> a >> b >> c >> d;
		path[a].pb(E.size());
		E.pb(b, c);
		path[b].pb(E.size());
		E.pb(a, d);
		ans[i] = INF;
	}
	solve();
	cin >> Q;
	for (int i = 1; i <= Q; i++) {
		cin >> a;
		cout << ans[a] << '\n';
	}
}

• Subtask 1: 0 / 6
• Subtask 2: 7 / 7
• Subtask 3: 0 / 9
• Subtask 4: 0 / 17
• Subtask 5: 0 / 17
• Subtask 6: 0 / 44