QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#723549#9230. Routing K-CodesSoestxWA 73ms34608kbC++233.1kb2024-11-07 22:50:352024-11-07 22:50:35

Judging History

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

  • [2024-11-07 22:50:35]
  • 评测
  • 测评结果:WA
  • 用时:73ms
  • 内存:34608kb
  • [2024-11-07 22:50:35]
  • 提交

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)
	{
		res=1e18;
		dfs(rt,-1),
		DFS(rt,-1,0,0,0);
	}
	if(res==1e18) 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: 0ms
memory: 19928kb

input:

4 3
1 2
1 3
1 4

output:

6

result:

ok single line: '6'

Test #2:

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

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: 16128kb

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: 73ms
memory: 34608kb

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:

858993459200000

result:

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