# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
311687 |
2020-10-11T03:18:57 Z |
shrek12357 |
Mag (COCI16_mag) |
C++14 |
|
1961 ms |
199544 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);
ll best = INT_MAX, nodes = 1;
const int MAXN = 1e6 + 5;
ll mag[MAXN];
vector<ll> adjList[MAXN];
ll dp[MAXN], dp1[MAXN];
void up(ll src, ll par) {
if (src != 0) {
dp1[src] += dp1[par];
}
if (mag[src] == 1) {
dp1[src]++;
}
else {
dp1[src] = 0;
}
for (auto i : adjList[src]) {
if (i == par) {
continue;
}
up(i, src);
}
}
void dfs(ll src, ll par) {
vector<ll> nums;
ll 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);
if (src != 0) {
nums.push_back(dp1[par]);
}
sort(nums.begin(), nums.end());
if (mag[src] == 1) {
ll 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) {
ll tot = nums[i] * 2 + 1;
if (best * tot > 2 * nodes) {
best = 2;
nodes = tot;
}
}
}
}
}
ll gcd(ll a, ll b) {
if (a < b) {
swap(a, b);
}
if (b == 0) {
return a;
}
return (a%b, b);
}
int main() {
ll n;
cin >> n;
for (int i = 0; i < n - 1; i++) {
ll 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]);
}
up(0, 0);
dfs(0, 0);
ll g = gcd(best, nodes);
ll finA = best / g, finB = nodes / g;
cout << finA << "/" << finB << endl;
}
Compilation message
mag.cpp: In function 'void dfs(long long int, long long int)':
mag.cpp:82:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | for (int i = 1; i < nums.size(); i++) {
| ~~^~~~~~~~~~~~~
mag.cpp: In function 'long long int gcd(long long int, long long int)':
mag.cpp:101:11: warning: left operand of comma operator has no effect [-Wunused-value]
101 | return (a%b, b);
| ~^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
23936 KB |
Output is correct |
2 |
Correct |
17 ms |
23936 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
18 ms |
23876 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1586 ms |
117856 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 |
1961 ms |
199544 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1803 ms |
78356 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1867 ms |
85340 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
231 ms |
29944 KB |
Output is correct |
2 |
Incorrect |
1804 ms |
79436 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1833 ms |
76848 KB |
Output is correct |
2 |
Incorrect |
1867 ms |
77888 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1817 ms |
79740 KB |
Output is correct |
2 |
Correct |
1156 ms |
54672 KB |
Output is correct |