# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
311685 | 2020-10-11T02:47:20 Z | shrek12357 | Mag (COCI16_mag) | C++14 | 1895 ms | 201456 KB |
#include <iostream> #include <vector> #include <algorithm> #include <string> #include <map> #include <set> #include <climits> #include <cmath> #include <fstream> #include <queue> #include <stack> #include <bitset> using namespace std; #define ll long long //cin.tie(0); //ios_base::sync_with_stdio(0);s int best = INT_MAX, nodes = 1; const int MAXN = 1e6 + 5; int mag[MAXN]; vector<int> adjList[MAXN]; int dp[MAXN]; void dfs(int src, int par) { vector<int> nums; int b1 = 0, b2 = 0; for (auto i : adjList[src]) { if (i == par) { continue; } dfs(i, src); nums.push_back(dp[i]); dp[src] = max(dp[src], dp[i]); if (dp[i] >= b1) { b2 = b1; b1 = dp[i]; } else if (dp[i] > b2) { b2 = dp[i]; } } if (mag[src] == 1) { dp[src]++; } else { dp[src] = 0; } nums.push_back(0); sort(nums.begin(), nums.end()); if (mag[src] == 1) { int tot = b1 + b2 + 1; if (best * tot > nodes) { nodes = tot; best = 1; } } if (mag[src] == 2) { if (nums.size() == 1) { return; } for (int i = 1; i < nums.size(); i++) { if (nums[i] - nums[i - 1] == 1) { int tot = nums[i] * 2; if (best * tot > 2 * nodes) { best = 2; nodes = tot; } } } } } int gcd(int a, int b) { if (a < b) { swap(a, b); } if (b == 0) { return a; } return (a%b, b); } int main() { int n; cin >> n; for (int i = 0; i < n - 1; i++) { int a, b; cin >> a >> b; a--; b--; adjList[a].push_back(b); adjList[b].push_back(a); } for (int i = 0; i < n; i++) { cin >> mag[i]; best = min(best, mag[i]); } dfs(0, 0); int g = gcd(best, nodes); int finA = best / g, finB = nodes / g; cout << finA << "/" << finB << endl; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 18 ms | 23808 KB | Output is correct |
2 | Correct | 17 ms | 23808 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 18 ms | 23808 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1538 ms | 119184 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 17 ms | 23808 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1895 ms | 201456 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1745 ms | 78336 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1810 ms | 83472 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 208 ms | 29304 KB | Output is correct |
2 | Incorrect | 1761 ms | 79300 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1657 ms | 78060 KB | Output is correct |
2 | Incorrect | 1823 ms | 79552 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1763 ms | 79484 KB | Output is correct |
2 | Correct | 1083 ms | 51588 KB | Output is correct |