| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 439805 |
2021-06-30T20:05:49 Z |
rainboy |
Mag (COCI16_mag) |
C |
|
527 ms |
162400 KB |
#include <stdio.h>
#include <stdlib.h>
#define N 1000000
int max(int a, int b) { return a > b ? a : b; }
int *ej[N], eo[N];
void append(int i, int j) {
int o = eo[i]++;
if (o >= 2 && (o & o - 1) == 0)
ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
ej[i][o] = j;
}
int aa[N], kk[N];
void dfs1(int p, int i) {
int o, k;
k = 0;
for (o = eo[i]; o--; ) {
int j = ej[i][o];
if (j != p) {
dfs1(i, j);
k = max(k, kk[j]);
}
}
kk[i] = aa[i] == 1 ? k + 1 : 0;
}
int p_, q_;
void dfs2(int p, int i, int k) {
int o, k1, k2, j1;
if (aa[i] == 1) {
q_ = max(q_, k + 1);
k1 = k2 = k, j1 = -1;
for (o = eo[i]; o--; ) {
int j = ej[i][o];
if (j != p) {
if (k1 < kk[j])
k2 = k1, k1 = kk[j], j1 = j;
else if (k2 < kk[j])
k2 = kk[j];
}
}
k1++, k2++;
} else
k1 = k2 = 0, j1 = -1;
for (o = eo[i]; o--; ) {
int j = ej[i][o];
if (j != p)
dfs2(i, j, j == j1 ? k2 : k1);
}
}
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
int main() {
int n, h, i, j, d;
scanf("%d", &n);
for (i = 0; i < n; i++)
ej[i] = (int *) malloc(2 * sizeof *ej[i]);
for (h = 0; h < n - 1; h++) {
scanf("%d%d", &i, &j), i--, j--;
append(i, j), append(j, i);
}
for (i = 0; i < n; i++)
scanf("%d", &aa[i]);
p_ = 1;
dfs1(-1, 0), dfs2(-1, 0, 0);
for (i = 0; i < n; i++)
if (aa[i] > 1) {
int o, k1, k2;
k1 = k2 = 0;
for (o = eo[i]; o--; ) {
j = ej[i][o];
if (k1 < kk[j])
k2 = k1, k1 = kk[j];
else if (k2 < kk[j])
k2 = kk[j];
}
if ((long long) p_ * (k1 + k2 + 1) > (long long) q_ * aa[i])
p_ = aa[i], q_ = k1 + k2 + 1;
}
d = gcd(p_, q_), p_ /= d, q_ /= d;
printf("%d/%d\n", p_, q_);
return 0;
}
Compilation message
mag.c: In function 'append':
mag.c:13:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
13 | if (o >= 2 && (o & o - 1) == 0)
| ~~^~~
mag.c: In function 'main':
mag.c:71:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
71 | scanf("%d", &n);
| ^~~~~~~~~~~~~~~
mag.c:75:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
75 | scanf("%d%d", &i, &j), i--, j--;
| ^~~~~~~~~~~~~~~~~~~~~
mag.c:79:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
79 | scanf("%d", &aa[i]);
| ^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
417 ms |
92432 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
497 ms |
158660 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
445 ms |
66152 KB |
Output is correct |
| 2 |
Correct |
353 ms |
48832 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
412 ms |
69196 KB |
Output is correct |
| 2 |
Correct |
73 ms |
7216 KB |
Output is correct |
| 3 |
Incorrect |
527 ms |
162400 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
79 ms |
6920 KB |
Output is correct |
| 2 |
Correct |
449 ms |
66756 KB |
Output is correct |
| 3 |
Correct |
392 ms |
34796 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
400 ms |
63764 KB |
Output is correct |
| 2 |
Correct |
444 ms |
67188 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
429 ms |
67136 KB |
Output is correct |
| 2 |
Correct |
358 ms |
34688 KB |
Output is correct |
