# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
556368 |
2022-05-03T03:40:15 Z |
Olympia |
Mag (COCI16_mag) |
C++17 |
|
1008 ms |
195004 KB |
#include <bits/stdc++.h>
using namespace std;
vector<int> val;
vector<int> parent;
vector<int> dp1, dp2, dp3;
//dp1 is the maximum path that goes down
//dp2 is the maximum path that does not necessarily go down
//dp3 is the maximum path that goes up (straight up)
void dfs (vector<vector<int> > &adj, int curNode, int prevNode) {
dp1[curNode] = (val[curNode] == 1);
for (int i: adj[curNode]) {
if (i != prevNode) {
dfs (adj, i, curNode);
dp1[curNode] = max(dp1[curNode], dp1[i] + 1);
}
}
if (val[curNode] != 1) {
dp1[curNode] = 0;
}
}
void dfs2 (vector<vector<int> > &adj, int curNode, int prevNode) {
parent[curNode] = prevNode;
dp2[curNode] = dp1[curNode];
vector<int> v;
for (int i: adj[curNode]) {
if (i != prevNode) {
dfs2(adj, i, curNode);
v.push_back(dp1[i]);
}
}
sort(v.begin(), v.end());
if (v.size() >= 2) {
dp2[curNode] = max(dp2[curNode], v.back() + v[v.size() - 2] + 1);
}
if (val[curNode] != 1) {
dp2[curNode] = 0;
}
}
void dfs3 (vector<vector<int> >&adj, int curNode, int prevNode) {
if (curNode != prevNode) {
dp3[curNode] = dp3[prevNode] + 1;
} else {
dp3[curNode] = 1;
}
if (val[curNode] != 1) {
dp3[curNode] = 0;
}
for (int i: adj[curNode]) {
if (i != prevNode) {
dfs3(adj, i, curNode);
}
}
}
int main() {
vector<vector<int> > adj;
int n;
cin >> n;
adj.resize(n), dp1.resize(n), dp2.resize(n), dp3.resize(n), parent.resize(n);
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
u--, v--;
adj[u].push_back(v), adj[v].push_back(u);
}
val.resize(n);
int myMin = INT_MAX;
for (int i = 0; i < n; i++) {
cin >> val[i];
myMin = min(myMin, val[i]);
}
if (myMin >= 2) {
cout << myMin << "/" << 1;
return 0;
}
dfs(adj, 0, 0);
dfs2(adj, 0, 0);
dfs3(adj, 0, 0);
int myMax2 = 0;
int myMax1 = 0;
for (int i = 0; i < n; i++) {
myMax1 = max(myMax1, dp2[i]);
if (val[i] == 2) {
vector<int> v;
for (int j: adj[i]) {
if (j == parent[i]) {
v.push_back(dp3[j]);
} else {
v.push_back(dp1[j]);
}
}
sort(v.begin(), v.begin());
reverse(v.begin(), v.end());
myMax2 = max(myMax2, v[0]);
if (v.size() >= 2) myMax2 = max(myMax2, v[0] + v[1]);
myMax2++;
}
}
cout << 2 << "/" << myMax2 << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
798 ms |
110424 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1008 ms |
195004 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
873 ms |
74768 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
906 ms |
78780 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
107 ms |
8524 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
834 ms |
71256 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
884 ms |
76292 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |