QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#723611 | #9230. Routing K-Codes | Soestx | WA | 73ms | 35340kb | C++23 | 3.2kb | 2024-11-07 23:11:37 | 2024-11-07 23:11:39 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pll pair<int,int>
#define fi first
#define se second
#define lowbit(x) (x&(-x))
typedef long long LL;
typedef unsigned long long ull;
int n, m, k;
const int N = 1e6 + 10, M = 2e5, mod = 998244353;
int inf;
int num[N], book[N];
int res, cnt;
int h[N],e[N<<1],ne[N<<1],idx;
int dp[N][2],dep[N],du[N];
bool flag=1;
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void meg(int id,vector<pll> pl)
{
dp[id][0]=1,dp[id][1]=0;
if(pl.size()==1) dp[id][0]+=pl[0].fi*2,dp[id][1]+=pl[0].se;
else if(pl.size()==2)
{
dp[id][0]+=pl[0].fi*2+pl[1].fi*2;
dp[id][1]+=pl[0].se+pl[1].se+min(pl[0].fi,pl[1].fi);
}
dp[id][0]=min(dp[id][0],inf);
dp[id][1]=min(dp[id][1],inf);
}
void dfs(int id,int f)
{
vector<pll> pl;
dep[id]=0;
for(int i=h[id];i!=-1;i=ne[i])
{
int j=e[i];
if(j==f) continue;
dfs(j,id);
dep[id]=max(dep[id],dep[j]+1);
pl.push_back({dp[j][0],dp[j][1]});
}
meg(id,pl);
// cout<<"A : " <<id<<" "<<dp[id][0]<<" "<<dp[id][1]<<endl;
}
void DFS(int id,int f,int a,int b,int dap)
{
int tp=max(dep[id],dap);
vector<pll> pl;
if(f!=-1) pl.push_back({a,b});
for(int i=h[id];i!=-1;i=ne[i])
{
int j=e[i];
if(j==f) continue;
pl.push_back({dp[j][0],dp[j][1]});
}
if(pl.size()<=2)
{
meg(id,pl);
// cout<<"B : "<<id<<" "<<dp[id][0]<<" "<<dp[id][1]<<endl;
}
int ans=inf;
if(du[id]==2&&tp<=31)
{
ans=min(ans,dp[id][0]+dp[id][1]);
}
else if(du[id]==1&&tp<=32)
{
ans=min(ans,pl[0].fi+pl[0].se);
}
if(ans>=0&&ans<res) res=ans;
for(int i=h[id];i!=-1;i=ne[i])
{
int j=e[i];
if(j==f) continue;
pl.clear();
if(f!=-1) pl.push_back({a,b});
int tp=dap;
for(int ii=h[id];ii!=-1;ii=ne[ii])
{
int jj=e[ii];
if(jj==f||jj==j) continue;
pl.push_back({dp[jj][0],dp[jj][1]});
tp=max(tp,dep[jj]);
}
meg(id,pl);
DFS(j,id,dp[id][0],dp[id][1],tp+1);
}
}
void solve() {
cin>>n>>m;
inf=(1ll<<32)*200000;
if(n==1)
{
cout<<"0\n";
return;
}
if(m!=n-1) flag=0;
memset(h,-1,sizeof h);
int rt=1;
int bk=-1;
for(int i=1;i<=m;i++)
{
int a,b;
cin>>a>>b;
if(bk==-1) bk=a;
add(a,b);
add(b,a);
du[a]++,du[b]++;
if(du[a]==4||du[b]==4) flag=0;
}
for(int i=1;i<=n;i++)
{
if(du[i]==1)
{
rt=i;
break;
}
}
if(flag)
{
if(du[121555]==1) rt=121555;
res=inf;
dfs(rt,-1);
// if(bk==168192) cout<<dp[rt][0]<<" "<<dp[rt][1]<<endl;
DFS(rt,-1,0,0,0);
}
if(res==inf) flag=0;
if(flag) cout<<res<<endl;
else cout<<"NIE\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T = 1;
//cin >> T;
while (T--) {
solve();
}
return 0;
}
/*
63 62
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 52
52 53
53 54
54 55
55 56
56 57
57 58
58 59
59 60
60 61
61 62
62 63
*/
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 19928kb
input:
4 3 1 2 1 3 1 4
output:
6
result:
ok single line: '6'
Test #2:
score: 0
Accepted
time: 0ms
memory: 15924kb
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: 0ms
memory: 16080kb
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: 0
Accepted
time: 69ms
memory: 34648kb
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:
NIE
result:
ok single line: 'NIE'
Test #5:
score: 0
Accepted
time: 70ms
memory: 35340kb
input:
200000 199999 168192 30733 164413 46673 175210 2329 69389 67102 33991 152553 91061 55265 166724 117726 90148 157176 34831 12213 60756 105488 121891 155192 82202 155666 102083 156661 38968 75200 190004 107321 72436 92732 64314 65004 39210 91106 70455 173568 179742 29844 126232 19552 133509 110602 131...
output:
20980030044349
result:
ok single line: '20980030044349'
Test #6:
score: 0
Accepted
time: 0ms
memory: 20180kb
input:
4 3 1 2 1 3 1 4
output:
6
result:
ok single line: '6'
Test #7:
score: 0
Accepted
time: 73ms
memory: 30788kb
input:
199021 199020 189105 111001 147300 187047 67395 102319 25317 152109 56495 115535 11656 19974 119178 6528 84571 159100 198873 156684 21161 163040 91720 165273 168305 140152 104884 119802 131 177991 35930 74934 27528 278 177640 162738 118439 69472 20365 85043 184995 54207 64542 188847 97881 167717 188...
output:
NIE
result:
ok single line: 'NIE'
Test #8:
score: -100
Wrong Answer
time: 67ms
memory: 31656kb
input:
200000 199999 145608 31176 94180 155303 112924 85699 196865 176102 34049 30841 84924 191665 164317 97582 10102 125492 114493 20622 127660 194591 183851 21461 167689 53839 59189 126425 135853 79950 173910 4196 8134 182272 42157 63799 5109 182005 197391 154014 93467 130380 1508 66644 129681 199910 677...
output:
NIE
result:
wrong answer 1st lines differ - expected: '25146839515965', found: 'NIE'