| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 682710 |
2023-01-16T20:24:26 Z |
as111 |
Mag (COCI16_mag) |
C++14 |
|
0 ms |
0 KB |
#include <iostream>
#include <vector>
#include <queue>
#include <map>
//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;
}
Compilation message
mag.cpp:17:15: error: 'LLONG_MAX' was not declared in this scope
17 | long long p = LLONG_MAX; // answer fraction
| ^~~~~~~~~
mag.cpp:5:1: note: 'LLONG_MAX' is defined in header '<climits>'; did you forget to '#include <climits>'?
4 | #include <map>
+++ |+#include <climits>
5 | //divide and conquer for a tree
mag.cpp: In function 'void dfs_path(int, int, int, long long int)':
mag.cpp:46:33: error: 'LLONG_MAX' was not declared in this scope
46 | if (temp[len] == 0)temp[len] = LLONG_MAX;
| ^~~~~~~~~
mag.cpp:46:33: note: 'LLONG_MAX' is defined in header '<climits>'; did you forget to '#include <climits>'?
mag.cpp: In function 'int main()':
mag.cpp:109:47: error: 'LLONG_MAX' was not declared in this scope
109 | if (mn[path.first] == 0) mn[path.first] = LLONG_MAX;
| ^~~~~~~~~
mag.cpp:109:47: note: 'LLONG_MAX' is defined in header '<climits>'; did you forget to '#include <climits>'?
