Submission #682711

#	Time	Username	Problem	Language	Result	Execution time	Memory
682711		as111	Mag (COCI16_mag)	C++14	0 / 120	466 ms	12924 KiB

mag

#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
• Subtask 2: 0 / 12
• Subtask 3: 0 / 12
• Subtask 4: 0 / 12
• Subtask 5: 0 / 12
• Subtask 6: 0 / 12
• Subtask 7: 0 / 12
• Subtask 8: 0 / 12
• Subtask 9: 0 / 12
• Subtask 10: 0 / 12