oj.uz

Submission #376154

# Submission time Handle Problem Language Result Execution time Memory
376154 2021-03-11T02:06:23 Z casperwang Designated Cities (JOI19_designated_cities) C++14
7 / 100
 355 ms 30024 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Incorrect 4 ms 5100 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 5 ms 5100 KB Output is correct
2 Correct 291 ms 20552 KB Output is correct
3 Correct 341 ms 29604 KB Output is correct
4 Correct 284 ms 20552 KB Output is correct
5 Correct 275 ms 20552 KB Output is correct
6 Correct 280 ms 21960 KB Output is correct
7 Correct 225 ms 20552 KB Output is correct
8 Correct 355 ms 30024 KB Output is correct
9 Correct 166 ms 21064 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Incorrect 290 ms 26696 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Incorrect 4 ms 5100 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5100 KB Output is correct
2 Correct 291 ms 20552 KB Output is correct
3 Correct 341 ms 29604 KB Output is correct
4 Correct 284 ms 20552 KB Output is correct
5 Correct 275 ms 20552 KB Output is correct
6 Correct 280 ms 21960 KB Output is correct
7 Correct 225 ms 20552 KB Output is correct
8 Correct 355 ms 30024 KB Output is correct
9 Correct 166 ms 21064 KB Output is correct
10 Correct 4 ms 5100 KB Output is correct
11 Incorrect 290 ms 26696 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Incorrect 4 ms 5100 KB Output isn't correct
3 Halted 0 ms 0 KB -