oj.uz

Submission #424516

# Submission time Handle Problem Language Result Execution time Memory
424516 2021-06-12T04:08:38 Z milleniumEeee Designated Cities (JOI19_designated_cities) C++17
6 / 100
 2000 ms 34052 KB 
#include <bits/stdc++.h>
#define fr first
#define sc second
#define pii pair<int, int>
#define pb push_back
#define szof(s) (int)s.size()
#define all(s) s.begin(), s.end()
#define fastInp ios_base::sync_with_stdio(0); cin.tie(0);
//#define ll long long

template<class T>void chmax(T &a, T b){if (a < b)a = b;}
template<class T>void chmin(T &a, T b){if (b < a)a = b;}

#define int long long

using namespace std;

const int MAXN  = (int)2e5 + 5;
const int INF = 1e18;

int A[MAXN], B[MAXN], C[MAXN], D[MAXN];
vector <pii> g[MAXN];
int n;

int tin[MAXN], tout[MAXN];
int tiktak = 0;

void dfs(int v, int par) {
	tin[v] = ++tiktak;
	for (auto [to, cost] : g[v]) {
		if (to != par) {
			dfs(to, v);
		}
	}
	tout[v] = tiktak;
}

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

int used[MAXN][2], used_id = 0;

void add(int x) {
	for (int i = 1; i < n; i++) {
		int a = A[i];
		int b = B[i];
		if (father(a, b)) {
			if (father(b, x)) {
				//cout << a << " -> " << b << endl;
				used[i][0] = used_id;
			} else {
				//cout << b << " -> " << a << endl;
				used[i][1] = used_id;
			}
		}
		else {
			if (father(a, x)) {
				//cout << b << " -> " << a << endl;
				used[i][1] = used_id;
			}
			else {
				//cout << a << " -> " << b << endl;
				used[i][0] = used_id;
			}
		}
	}
}

int calc_ans() {
	int sum = 0;
	for (int i = 1; i < n; i++) {
		if (used[i][0] != used_id) {
			sum += C[i];
		}
		if (used[i][1] != used_id) {
			sum += D[i];
		}
	}
	return sum;
}

int ans[20];

void precalc() {
	fill(ans, ans + 20, INF);
	for (int mask = 1; mask < (1 << 16); mask++) {
		used_id++;
		for (int i = 0; i < 16; i++) {
			if (mask & (1 << i)) {
				add(i + 1);
			}
		}
		int bits = __builtin_popcount(mask);
		chmin(ans[bits], calc_ans());
	}
}

signed main() {
	//freopen("file.in", "r", stdin);
	fastInp;
	cin >> n;
	for (int i = 1; i < n; i++) {
		cin >> A[i] >> B[i] >> C[i] >> D[i];
		g[A[i]].pb({B[i], C[i]});
		g[B[i]].pb({A[i], D[i]});
	}
	dfs(1, -1);
	precalc();
	int q;
	cin >> q;
	while (q--) {
		int e;
		cin >> e;
		cout << ans[e] << endl;
	}
}

/*
4
1 2 1 2
1 3 3 4
1 4 5 6
2
1 
2

*/

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 4940 KB Output is correct
2 Correct 30 ms 5048 KB Output is correct
3 Correct 28 ms 5060 KB Output is correct
4 Correct 29 ms 5028 KB Output is correct
5 Correct 29 ms 5064 KB Output is correct
6 Correct 31 ms 4940 KB Output is correct
7 Correct 33 ms 4940 KB Output is correct
8 Correct 30 ms 5056 KB Output is correct
9 Correct 30 ms 4940 KB Output is correct
10 Correct 32 ms 4940 KB Output is correct
11 Correct 40 ms 5008 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 5032 KB Output is correct
2 Execution timed out 2074 ms 34048 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 4940 KB Output is correct
2 Execution timed out 2085 ms 34052 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 4940 KB Output is correct
2 Correct 30 ms 5048 KB Output is correct
3 Correct 28 ms 5060 KB Output is correct
4 Correct 29 ms 5028 KB Output is correct
5 Correct 29 ms 5064 KB Output is correct
6 Correct 31 ms 4940 KB Output is correct
7 Correct 33 ms 4940 KB Output is correct
8 Correct 30 ms 5056 KB Output is correct
9 Correct 30 ms 4940 KB Output is correct
10 Correct 32 ms 4940 KB Output is correct
11 Correct 40 ms 5008 KB Output is correct
12 Correct 11 ms 5064 KB Output is correct
13 Execution timed out 2078 ms 5324 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 5032 KB Output is correct
2 Execution timed out 2074 ms 34048 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 4940 KB Output is correct
2 Correct 30 ms 5048 KB Output is correct
3 Correct 28 ms 5060 KB Output is correct
4 Correct 29 ms 5028 KB Output is correct
5 Correct 29 ms 5064 KB Output is correct
6 Correct 31 ms 4940 KB Output is correct
7 Correct 33 ms 4940 KB Output is correct
8 Correct 30 ms 5056 KB Output is correct
9 Correct 30 ms 4940 KB Output is correct
10 Correct 32 ms 4940 KB Output is correct
11 Correct 40 ms 5008 KB Output is correct
12 Correct 10 ms 5032 KB Output is correct
13 Execution timed out 2074 ms 34048 KB Time limit exceeded
14 Halted 0 ms 0 KB -