QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#84853#5651. Parmigiana With Seafoodsinsop90WA 3ms7616kbC++141.1kb2023-03-06 20:17:342023-03-06 20:17:45

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-06 20:17:45]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:7616kb
  • [2023-03-06 20:17:34]
  • 提交

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'