QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#723611#9230. Routing K-CodesSoestxWA 73ms35340kbC++233.2kb2024-11-07 23:11:372024-11-07 23:11:39

Judging History

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

  • [2024-11-07 23:11:39]
  • 评测
  • 测评结果:WA
  • 用时:73ms
  • 内存:35340kb
  • [2024-11-07 23:11:37]
  • 提交

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'