QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#84853 | #5651. Parmigiana With Seafood | sinsop90 | WA | 3ms | 7616kb | C++14 | 1.1kb | 2023-03-06 20:17:34 | 2023-03-06 20:17:45 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 5;
int head[maxn], fa[maxn], dis[maxn], ans, t1, t2, tot, n, t[maxn], vis[maxn], out[maxn];
struct node {
int v, pre;
}e[maxn << 1];
void add(int u, int v) {
e[++ tot].v = v;
e[tot].pre = head[u];
head[u] = tot;
}
void dfs(int now, int f) {
fa[now] = f;
for(int i = head[now];i;i = e[i].pre) {
int v = e[i].v;
if(v == f) continue;
dis[v] = dis[now] ^ 1;
dfs(v, now);
}
}
int main() {
scanf("%d", &n);
if(n % 2 == 0) {
printf("%d\n", n);
return 0;
}
for(int i = 1, u, v;i < n;i++) {
scanf("%d%d", &u, &v);
add(u, v), add(v, u);
out[u] ++, out[v] ++;
}
dfs(n, 0);
for(int i = n - 1;i >= 1;i--) {
if(dis[i] || out[i] == 1) {
printf("%d\n", i);
return 0;
}
int now = i;
while(1) {
t[now] ++;
if(vis[now]) break;
vis[now] = 1;
now = fa[now];
t[now] ++;
}
// cout << now << " " << t[now] << endl;
if(t[now] > 2 && !dis[now]) {
printf("%d\n", i);
return 0;
}
}
printf("%d\n", max(ans, min(t1, t2)));
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 5532kb
input:
4 1 2 1 3 1 4
output:
4
result:
ok single line: '4'
Test #2:
score: -100
Wrong Answer
time: 3ms
memory: 7616kb
input:
5 1 5 5 3 3 4 4 2
output:
4
result:
wrong answer 1st lines differ - expected: '3', found: '4'