oj.uz

Submission #682711

# Submission time Handle Problem Language Result Execution time Memory
682711 2023-01-16T20:25:03 Z as111 Mag (COCI16_mag) C++14
0 / 120
 466 ms 12924 KB 
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <climits>
//divide and conquer for a tree
#define MAXN 100000

using namespace std;
vector<int> adj[MAXN + 5];
int N;
long long mag[MAXN + 5];

bool deleted[MAXN + 5]; // deleted after centroid marked
int sz[MAXN + 5]; // size of subtree
int head[MAXN + 5]; // head of subtree to find centroid for
queue<int> Q;
long long p = LLONG_MAX; // answer fraction
long long q = 1;
int gcd(int a, int b) {
	if (b == 0)
		return a;
	return gcd(b, a % b);
}
void comp(long long num, long long den) { // find min fraction
	long long factor = gcd(num, den);
	num /= factor;
	den /= factor;
	if (num * q < den * p) {
		p = num;
		q = den;
	}
}
void dfs(int x, int p, int h) { // find size for subtree
	sz[x] = 1; // reset size
	head[x] = h;
	for (int e : adj[x]) {
		if (deleted[e]) continue;
		if (e == p) continue;
		dfs(e, x, h);
		sz[x] += sz[e];
	}
}
map<int, long long> mn; // max possible product for each path length
map<int, long long> temp; // current childs subtree, compare with max for all the other children
void dfs_path(int x, int p, int len, long long prod) { // length and product of current path
	if (temp[len] == 0)temp[len] = LLONG_MAX;
	temp[len] = min(temp[len], prod);
	for (int e : adj[x]) {
		if (deleted[e]) continue;
		if (e == p) continue;
		dfs_path(e, x, len + 1, prod * mag[e]);
	}
}
void dfs_comp(int x, int p, int len, long long prod) { // compare with other paths
	for (auto path : mn) {
		comp(prod * path.second, len + path.first);
	}
	for (int e : adj[x]) {
		if (deleted[e]) continue;
		if (e == p) continue;
		dfs_comp(e, x, len + 1, prod * mag[e]);
	}
}
int find(int x, int p, int h) { // return centroid for suntree starting at x, h head of tree
	bool cent = true;
	int centroid = -1;
	if ((sz[h] - sz[x]) > sz[h] / 2) {
		cent = false;
	}
	for (int e : adj[x]) {
		if (deleted[e]) continue;
		if (e == p) continue;
		if (sz[e] > sz[h] / 2) cent = false;
	}
	if (cent) {
		return x;
	}
	else {
		for (int e : adj[x]) {
			if (deleted[e]) continue;
			if (e == p) continue;
			centroid = max(centroid, find(e, x, h));
		}
		return centroid;
	}
}
int main() {
	cin >> N;
	for (int i = 1; i < N; i++) {
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	for (int i = 1; i <= N; i++) {
		cin >> mag[i];
	}
	Q.push(1);
	while (!Q.empty()) {
		int curr = Q.front(); Q.pop();
		dfs(curr, -1, curr);
		int centroid = find(curr, -1, curr);
		for (int c : adj[centroid]) {
			if (deleted[c]) continue;
			dfs_path(c, centroid, 1, mag[c]);
			mn[0] = 1; // for only using the path and centroid
			dfs_comp(c, centroid, 2, mag[c]*mag[centroid]);
			for (auto path : temp) {
				if (mn[path.first] == 0) mn[path.first] = LLONG_MAX;
				mn[path.first] = min(mn[path.first], temp[path.first]);
			}
			temp.clear();
			Q.push(c);
		}
		mn.clear();
		deleted[centroid] = true;
	}
	cout << p << "/" << q;
}

Subtask #1
0 / 12.0

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

Subtask #2
0 / 12.0

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

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 5204 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Runtime error 62 ms 12904 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 65 ms 12832 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 5204 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 5224 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 466 ms 8964 KB Output is correct
2 Runtime error 5 ms 5204 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 5216 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 65 ms 12924 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -