| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 701617 |
2023-02-21T15:21:17 Z |
Do_you_copy |
Mag (COCI16_mag) |
C++17 |
|
452 ms |
211476 KB |
#include <bits/stdc++.h>
#define fi first
#define se second
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
#define pb push_back
using namespace std;
using ll = long long;
using pii = pair <int, int>;
const int maxN = 2e6 + 1;
const int inf = 0x3f3f3f3f;
//const int Mod =
int n;
int a[maxN];
vector <int> adj[maxN];
int dp[maxN][2];
struct TFrac{
int x, y;
bool operator < (const TFrac other) const{
//x / y < other.x / other.y;
//x * other.y < other.x * y;
return x * other.y < other.x * y;
}
};
TFrac ans = {1, 1};
void update(pair <pii, pii> &x, pii y){
if (y > x.fi){
swap(x.fi, x.se);
x.fi = y;
}
else x.se = max(x.se, y);
}
void dfs(int u, int p){
for (int i: adj[u]){
if (i == p) continue;
dfs(i, u);
}
if (a[u] > 2) return;
if (a[u] == 1){
pair <pii, pii> max1 = {{0, 0}, {0, 0}};
pair <pii, pii> max2 = {{0, 0}, {0, 0}};
for (int i: adj[u]){
if (i == p) continue;
update(max1, {dp[i][0], i});
update(max2, {dp[i][1], i});
}
TFrac tem1 = {1, max1.fi.fi + max1.se.fi + 1};
TFrac tem2;
if (max1.fi.se == max2.fi.se){
tem2.x = 2;
tem2.y = 1 + max(max1.fi.fi + max2.se.fi, max1.se.fi + max2.fi.fi);
}
else{
tem2.x = 2;
tem2.y = 1 + max1.fi.fi + max2.fi.fi;
}
tem1 = min(tem1, tem2);
ans = min(ans, tem1);
dp[u][1] = 1 + max2.fi.fi;
dp[u][0] = 1 + max1.fi.fi;
}
else{
pii max1 = {0, 0};
for (int i: adj[u]){
if (i == p) continue;
if (dp[i][0] > max1.fi){
swap(max1.fi, max1.se);
max1.fi = dp[i][0];
}
else max1.se = max(max1.se, dp[i][0]);
}
TFrac tem = {2, max1.fi + max1.se + 1};
ans = min(ans, tem);
dp[u][1] = 1 + max1.fi;
}
if (u == 1) cerr << dp[u][0] << ":D";
}
void Init(){
cin >> n;
for (int i = 1; i < n; ++i){
int u, v;
cin >> u >> v;
adj[u].pb(v);
adj[v].pb(u);
}
for (int i = 1; i <= n; ++i){
cin >> a[i];
}
if (*min_element(a + 1, a + n + 1) > 1){
cout << *min_element(a + 1, a + n + 1) << "/" << 1;
return;
}
dfs(1, 0);
int gcd = __gcd(ans.x, ans.y);
ans.x /= gcd;
ans.y /= gcd;
cout << ans.x << "/" << ans.y;
}
#define taskname "test"
signed main(){
faster
if (fopen(taskname ".inp", "r")){
freopen(taskname ".inp", "r", stdin);
freopen(taskname ".out", "w", stdout);
}
int tt = 1;
//cin >> tt;
while (tt--){
Init();
}
if (fopen("timeout.txt", "r")){
ofstream timeout("timeout.txt");
cerr << "Time elapsed: " << signed(double(clock()) / CLOCKS_PER_SEC * 1000) << "ms\n";
timeout << signed(double(clock()) / CLOCKS_PER_SEC * 1000);
timeout.close();
}
}
Compilation message
mag.cpp: In function 'int main()':
mag.cpp:106:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
106 | freopen(taskname ".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mag.cpp:107:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
107 | freopen(taskname ".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
47316 KB |
Output is correct |
| 2 |
Correct |
25 ms |
47348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
47304 KB |
Output is correct |
| 2 |
Correct |
30 ms |
47356 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
318 ms |
126776 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
47276 KB |
Output is correct |
| 2 |
Correct |
401 ms |
204488 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
449 ms |
201756 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
367 ms |
91380 KB |
Output is correct |
| 2 |
Correct |
248 ms |
80272 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
317 ms |
91216 KB |
Output is correct |
| 2 |
Correct |
76 ms |
52888 KB |
Output is correct |
| 3 |
Correct |
452 ms |
211476 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
92 ms |
51964 KB |
Output is correct |
| 2 |
Correct |
321 ms |
92116 KB |
Output is correct |
| 3 |
Correct |
259 ms |
70436 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
292 ms |
89408 KB |
Output is correct |
| 2 |
Correct |
300 ms |
89444 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
320 ms |
91156 KB |
Output is correct |
| 2 |
Correct |
262 ms |
70388 KB |
Output is correct |
