QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#628539#9230. Routing K-Codeslucky_cloudWA 80ms23148kbC++142.4kb2024-10-10 20:50:572024-10-10 20:51:00

Judging History

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

  • [2024-10-10 20:51:00]
  • 评测
  • 测评结果:WA
  • 用时:80ms
  • 内存:23148kb
  • [2024-10-10 20:50:57]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 2e5 + 5;
int n, m, du[N], ans = 1e18, rt;
vector<int> g[N];
bool vis[N], flag;
struct dpnode {
    int k, b;
    int dep;
} dp[N];

void merge(dpnode &x, dpnode y) { x = {y.k * 2 + 1, y.b * 2, y.dep + 1}; }
void merge(dpnode &x, dpnode y, dpnode z) {
    x.k = 1 + 2 * (y.k + z.k);
    x.b = 2 * (y.b + z.b) + min(y.k, z.k);
    x.dep = max(y.dep, z.dep) + 1;
}
void dfs(int x, int fa) {
    if (vis[x]) return (void)(flag = 1);
    vis[x] = 1;
    for (int y : g[x]) if (y ^ fa) dfs(y, x);
}
void dfs1(int x, int fa) {
    int cnt = 0, son[3];
    for (int y : g[x]) if (y ^ fa) dfs1(y, x), son[++cnt] = y;
    if (!cnt) dp[x] = {1, 0, 1};
    if (cnt == 1) merge(dp[x], dp[son[1]]);
    if (cnt == 2) merge(dp[x], dp[son[1]], dp[son[2]]);
}
void dfs2(int x, int fa, dpnode dpf) {
    int cnt = 0, son[3];
    for (int y : g[x]) if (y ^ fa) son[++cnt] = y;
    dpnode now;
    if (du[x] < 3) {
        if (cnt == 0) {
            if (dpf.dep <= 32)
            ans = min(ans, dpf.k + dpf.b);
        }
        if (cnt == 1) {
            merge(now, dpf, dp[son[1]]);
            if (now.dep <= 32)
            ans = min(ans, now.k + now.b);
        }
    }
    if (cnt == 2) {
        merge(now, dp[son[2]], dpf);
        dfs2(son[1], x, now);
        merge(now, dp[son[1]], dpf);
        dfs2(son[2], x, now);
    }
    merge(now, dpf);
    if (cnt == 1) dfs2(son[1], x, now);
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    if (n == 1) {
        cout << "0\n";
        return 0;
    }
    for (int i = 1; i <= m; ++i) {
        int x, y; cin >> x >> y;
        g[x].push_back(y), g[y].push_back(x);
        du[x]++, du[y]++;
    }
    dfs(1, 0);
    if (flag) {
        cout << "NIE\n";
        return 0;
    }
    for (int i = 1; i <= n; ++i) {
        if (du[i] > 3) {
            cout << "NIE\n";
            return 0;
        }
    }
    for (int i = 1; i <= n; ++i) {
        if (du[i] < 3) {
            dfs1(i, 0);
            rt = i;
            break;
        }
    }
    dfs2(rt, 0, {0, 0, 0});
    if (g[rt].size() == 1 && dp[g[rt][0]].dep <= 32) ans = min(ans, dp[g[rt][0]].k + dp[g[rt][0]].b);
    if (g[rt].size() == 2 && dp[rt].dep <= 32) ans = min(ans, dp[rt].k + dp[rt].b);
    cout << ans << '\n';
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 9804kb

input:

4 3
1 2
1 3
1 4

output:

6

result:

ok single line: '6'

Test #2:

score: 0
Accepted
time: 2ms
memory: 9804kb

input:

4 6
1 2
2 3
3 4
4 1
1 3
2 4

output:

NIE

result:

ok single line: 'NIE'

Test #3:

score: 0
Accepted
time: 2ms
memory: 9792kb

input:

10 10
9 3
5 10
1 4
10 8
8 3
7 3
9 6
8 6
7 2
4 5

output:

NIE

result:

ok single line: 'NIE'

Test #4:

score: -100
Wrong Answer
time: 80ms
memory: 23148kb

input:

200000 199999
172774 188052
195063 155577
38023 148303
30605 155047
170238 19344
46835 58255
154268 109062
197059 116041
136424 12058
42062 149807
109545 115380
132322 51106
16706 162612
62234 31319
195735 80435
173898 84051
19876 102910
186924 9136
123094 117097
145054 173049
137364 152731
82662 18...

output:

1000000000000000000

result:

wrong answer 1st lines differ - expected: 'NIE', found: '1000000000000000000'