QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#84482#5651. Parmigiana With Seafooda_z_cWA 30ms9852kbC++231.3kb2023-03-06 15:20:272023-03-06 15:20:55

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 15:20:55]
  • 评测
  • 测评结果:WA
  • 用时:30ms
  • 内存:9852kb
  • [2023-03-06 15:20:27]
  • 提交

answer

// Problem: Parmigiana With Seafood
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1776M
// Memory Limit: 250 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
vector<int> G[maxn];
int col[maxn];
int n;
void dfs(int u, int fa) {
    col[u] = col[fa] ^ 1;
    for (int v : G[u]) {
        if (v == fa)
            continue;
        dfs(v, u);
    }
}
vector<int> m0, m1;
int ans;
int main() {
    scanf("%d", &n);
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }
    if (!(n & 1)) {
        printf("%d", n);
        return 0;
    }
    dfs(1, 1);
    for (int i = n; i > 0; i--) {
        if (col[i] && m1.size() < 3) {
            m1.emplace_back(i);
        }
        if (!col[i] && m0.size() < 3) {
            m0.emplace_back(i);
        }
        if (G[i].size() <= 1) {
            ans = max(ans, i);
        }
    }
    if (m1.size() && m0.size())
        ans = max(ans, min(m1[0], m0[0]));
    if (m1.size() > 2)
        ans = max(ans, m1[2]);
    if (m0.size() > 2)
        ans = max(ans, m0[2]);
    printf("%d", ans);
}//12231

详细

Test #1:

score: 100
Accepted
time: 3ms
memory: 5848kb

input:

4
1 2
1 3
1 4

output:

4

result:

ok single line: '4'

Test #2:

score: 0
Accepted
time: 3ms
memory: 5924kb

input:

5
1 5
5 3
3 4
4 2

output:

3

result:

ok single line: '3'

Test #3:

score: -100
Wrong Answer
time: 30ms
memory: 9852kb

input:

99999
81856 39633
81856 94012
99999 43062
99946 220
81856 46131
99933 36505
99939 35662
99952 70971
99999 3275
99938 58416
99976 66658
99991 87922
81856 80992
99933 6392
99951 41047
99970 54115
81856 38150
99934 73554
81856 64578
81856 18576
99951 67996
99938 84479
81856 39617
99999 18664
99946 2505...

output:

99997

result:

wrong answer 1st lines differ - expected: '99925', found: '99997'