QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#628539 | #9230. Routing K-Codes | lucky_cloud | WA | 80ms | 23148kb | C++14 | 2.4kb | 2024-10-10 20:50:57 | 2024-10-10 20:51:00 |
Judging History
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'