# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
240548 |
2020-06-19T22:14:56 Z |
thecodingwizard |
Mag (COCI16_mag) |
C++11 |
|
1751 ms |
252612 KB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n;
ll A[1000000];
vector<int> adj[1000000];
ll num = 100000000000;
ll denom = 1;
int memoMaxOnesInLine[1000000];
int maxOnesInLine(int u, int p) {
if (memoMaxOnesInLine[u] != -1) return memoMaxOnesInLine[u];
if (A[u] != 1) return 0;
int ans = 1;
for (int v : adj[u]) {
if (v != p) ans = max(ans, 1 + maxOnesInLine(v, u));
}
return memoMaxOnesInLine[u] = ans;
}
int maxOnesOnly(int u, int p) {
int best = 0;
if (A[u] == 1) {
vector<int> childrenOnesCount;
for (int v : adj[u]) {
if (v != p) {
childrenOnesCount.push_back(maxOnesInLine(v, u));
}
}
sort(childrenOnesCount.begin(), childrenOnesCount.end());
best = 1;
if (childrenOnesCount.size()>=1) best = childrenOnesCount[childrenOnesCount.size()-1] + 1;
if (childrenOnesCount.size()>=2) best += childrenOnesCount[childrenOnesCount.size()-2];
}
for (int v : adj[u]) {
if (v != p) {
best = max(best, maxOnesOnly(v, u));
}
}
return best;
}
int maxOnesWithTwo(int u, int p, int numOnesFromParent) {
int best = 0;
int parentOnes = 0;
vector<int> childrenOnesCount;
for (int v : adj[u]) {
if (v != p) {
childrenOnesCount.push_back(maxOnesInLine(v, u));
}
}
childrenOnesCount.push_back(numOnesFromParent);
childrenOnesCount.push_back(0);
sort(childrenOnesCount.begin(), childrenOnesCount.end());
if (A[u] == 2) {
best = childrenOnesCount[childrenOnesCount.size()-1] + childrenOnesCount[childrenOnesCount.size()-2] + 1;
} else if (A[u] == 1) {
parentOnes = 1 + numOnesFromParent;
parentOnes = max(parentOnes, childrenOnesCount.back() + 1);
}
for (int v : adj[u]) {
// warning: parentOnes will be wrong for one node...
if (v != p) {
if (childrenOnesCount.back() != childrenOnesCount[childrenOnesCount.size()-2]) {
if (maxOnesInLine(v, u) == childrenOnesCount.back() && A[u] == 1) {
best = max(best, maxOnesWithTwo(v, u, max(numOnesFromParent+1, childrenOnesCount[childrenOnesCount.size()-2]+1)));
} else {
best = max(best, maxOnesWithTwo(v, u, parentOnes));
}
} else {
best = max(best, maxOnesWithTwo(v, u, parentOnes));
}
}
}
return best;
}
int main() {
cin >> n;
for (int i = 0; i < n-1; i++) {
int a, b; cin >> a >> b;
--a; --b;
adj[a].push_back(b);
adj[b].push_back(a);
}
for (int i = 0; i < n; i++) cin >> A[i];
num = A[0];
for (int i = 0; i < n; i++) {
num = min(num, A[i]);
}
for (int i = 0; i < n; i++) {
memoMaxOnesInLine[i] = -1;
}
// case 1: all ones
int numOnes = maxOnesOnly(0, 0);
// case 2: one two
int numOnesWithTwo = maxOnesWithTwo(0, 0, 0);
if (numOnes==0 || 1.0/numOnes > num) {
if (numOnesWithTwo==0 || 2.0/numOnesWithTwo > num) {
cout << num << "/" << 1 << endl;
} else {
if (numOnesWithTwo%2==0) {
cout << "1/" << numOnesWithTwo/2 << endl;
} else {
cout << "2/" << numOnesWithTwo << endl;
}
}
} else {
if (numOnesWithTwo==0 || 2.0/numOnesWithTwo > 1.0/numOnes) {
cout << "1/" << numOnes << endl;
} else {
if (numOnesWithTwo%2==0) {
cout << "1/" << numOnesWithTwo/2 << endl;
} else {
cout << "2/" << numOnesWithTwo << endl;
}
}
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
23808 KB |
Output is correct |
2 |
Correct |
21 ms |
23808 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
23808 KB |
Output is correct |
2 |
Correct |
21 ms |
23808 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1386 ms |
127172 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
23808 KB |
Output is correct |
2 |
Correct |
1717 ms |
252612 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1705 ms |
233800 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1431 ms |
66924 KB |
Output is correct |
2 |
Correct |
1053 ms |
55776 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1487 ms |
71164 KB |
Output is correct |
2 |
Correct |
196 ms |
28280 KB |
Output is correct |
3 |
Correct |
1751 ms |
239224 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
225 ms |
28280 KB |
Output is correct |
2 |
Correct |
1417 ms |
68472 KB |
Output is correct |
3 |
Correct |
912 ms |
46048 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1391 ms |
66288 KB |
Output is correct |
2 |
Correct |
1509 ms |
66296 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1465 ms |
67868 KB |
Output is correct |
2 |
Correct |
945 ms |
53624 KB |
Output is correct |