QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#292998#7600. Minimums on the EdgesPhantomThreshold#ML 812ms321804kbC++171.9kb2023-12-28 19:20:462023-12-28 19:20:47

Judging History

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

  • [2023-12-28 19:20:47]
  • 评测
  • 测评结果：ML
  • 用时：812ms
  • 内存：321804kb
查看
  • [2023-12-28 19:20:46]
  • 提交

answer

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

const int maxn = 20;
const int mask = 1<<18;
const int inf  = 1e9;

int n,m,K,N;
int a[maxn][maxn];
int cnt[maxn][mask];

vector< vector<int> >f[mask],g[mask],gi[mask];

//f[mask][i][j]
//  s    min sum

void output()
{
	vector<int>ans(n+5);
	{
		int s=N-1;
		int mn,sum=K,temp=-inf;
		for(int i=0;i<=K;i++)
		{
			if(f[s][i][sum]>temp)
			{
				temp=f[s][i][sum];
				mn=i;
			}
		}
	//	cerr<<temp<<endl;
		while(s)
		{
			int i=gi[s][mn][sum];
			int tn=g[s][mn][sum];
			ans[i]=mn;
			sum-=mn;
			mn=tn;
			s^=1<<(i-1);
		}
	}
	for(int i=1;i<=n;i++) cout<<ans[i]<<" \n"[i==n];
}

int main()
{
	ios_base::sync_with_stdio(false);
	
	cin>>n>>m>>K;
	N=1<<n;
	for(int i=1;i<=m;i++)
	{
		int x,y; cin>>x>>y;
		a[x][y]++;
		a[y][x]++;
	}
	for(int i=1;i<=n;i++)
	{
		cnt[i][0]=0;
		for(int s=1;s<N;s++)
		{
			for(int j=1;j<=n;j++) if(s>>(j-1)&1)
			{
				cnt[i][s]=cnt[i][s^1<<(j-1)]+a[i][j];
				break;
			}
		}
	}
	
//	f.resize(0+5); g.resize(0+5);
//	f[0].resize(0+5),g[0].resize(0+5);
	for(int s=0;s<N;s++)
	{
		int num=__builtin_popcount(s);
		
		int umn = K/(n-num+1);
		f[s].resize( umn+3 ); g[s].resize( umn+3 ); gi[s].resize(umn+3);
		for(int mn=0;mn<=umn;mn++)
		{
			int usum= K-mn*(n-num);
			f[s][mn].resize(usum+3);
			g[s][mn].resize(usum+3);
			gi[s][mn].resize(usum+3);
			for(int sum=mn;sum<=usum;sum++)
			{
				f[s][mn][sum]=-inf;
				for(int i=1;i<=n;i++) if(s>>(i-1)&1)
				{
					int ts=s^1<<(i-1);
					for(int tn=0;tn<=mn&&tn<=sum-mn;tn++) 
					if(f[ts][tn][sum-mn]!=-inf)
					{
						int temp= f[ts][tn][sum-mn]+mn*cnt[i][(N-1)^s];
						if( f[s][mn][sum]<temp )
						{
							f[s][mn][sum]=temp;
							g[s][mn][sum]=tn;
							gi[s][mn][sum]=i;
						}
					}
				}
			}
		}
		if(s==0) f[s][0][0]=0;
	}
	
	output();
	
	return 0;
}
Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 26336kb

input:

4 4 6
1 2
2 3
3 1
1 4

output:

2 2 2 0

result:

ok answer = 6

Test #2:

score: 0
Accepted
time: 4ms
memory: 26604kb

input:

3 7 7
1 2
1 2
1 2
1 3
1 3
2 3
2 3

output:

3 2 2

result:

ok answer = 14

Test #3:

score: 0
Accepted
time: 0ms
memory: 29152kb

input:

5 10 61
5 3
1 2
4 5
2 3
2 1
3 1
1 5
3 5
2 4
2 1

output:

13 13 13 9 13

result:

ok answer = 122

Test #4:

score: 0
Accepted
time: 4ms
memory: 28980kb

input:

5 10 6
1 4
3 4
4 3
1 4
5 1
4 3
3 2
1 3
5 2
2 3

output:

2 0 2 2 0

result:

ok answer = 12

Test #5:

score: 0
Accepted
time: 3ms
memory: 28236kb

input:

5 10 85
3 1
4 5
4 1
4 5
1 5
2 3
4 5
1 4
3 2
2 3

output:

17 17 17 17 17

result:

ok answer = 170

Test #6:

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

input:

5 10 30
2 5
2 4
4 5
4 3
5 1
4 3
2 3
1 5
1 4
2 1

output:

6 6 6 6 6

result:

ok answer = 60

Test #7:

score: 0
Accepted
time: 7ms
memory: 28476kb

input:

5 10 77
1 3
4 1
4 3
5 2
5 2
2 5
2 3
3 4
5 3
5 2

output:

13 16 16 16 16

result:

ok answer = 154

Test #8:

score: 0
Accepted
time: 10ms
memory: 34600kb

input:

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

output:

0 0 0 0 1 1 1 1 0 0

result:

ok answer = 1415

Test #9:

score: 0
Accepted
time: 59ms
memory: 45508kb

input:

10 10000 83
7 9
6 4
3 6
7 5
2 5
10 7
10 7
7 10
6 5
3 9
2 6
9 10
8 2
6 2
10 1
3 9
4 2
9 5
2 10
6 3
10 5
5 9
6 2
1 4
8 9
7 6
2 5
7 8
10 4
2 1
2 9
7 10
2 7
2 5
9 10
10 8
4 1
10 8
2 5
3 10
6 7
6 3
5 8
10 2
6 10
6 3
9 5
6 2
8 5
8 2
8 10
2 8
5 10
5 2
10 3
8 6
3 1
3 2
8 7
3 7
8 2
9 7
5 9
5 3
7 5
2 6
6 9
8 ...

output:

8 8 8 8 8 8 9 8 9 9

result:

ok answer = 80726

Test #10:

score: 0
Accepted
time: 8ms
memory: 35224kb

input:

10 10000 28
8 3
7 5
10 9
6 2
1 9
4 7
4 7
7 1
10 6
10 5
5 3
8 3
3 1
3 1
8 1
4 7
5 6
4 10
3 2
4 8
2 4
9 7
8 7
10 9
9 10
2 1
6 1
7 1
2 8
5 10
1 4
5 8
1 3
8 3
4 3
9 2
5 1
4 6
10 1
10 2
5 4
9 3
10 2
5 9
2 1
7 4
1 8
4 8
3 9
9 6
3 6
5 1
2 7
4 3
2 8
8 10
1 7
4 1
3 9
1 2
1 9
8 4
9 5
1 5
6 4
1 6
6 7
2 7
10 4
...

output:

3 3 3 2 3 2 3 3 3 3

result:

ok answer = 26312

Test #11:

score: 0
Accepted
time: 0ms
memory: 34184kb

input:

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

output:

1 0 1 1 0 0 1 0 1 1

result:

ok answer = 3460

Test #12:

score: 0
Accepted
time: 13ms
memory: 34368kb

input:

10 10000 19
1 3
6 7
4 5
9 8
5 8
1 9
10 7
10 6
2 9
2 5
2 4
2 3
3 2
9 3
3 9
7 10
7 8
7 1
8 6
8 9
1 5
2 5
4 6
2 10
8 9
8 2
6 7
9 10
1 2
3 10
5 6
8 5
5 9
3 4
4 10
5 3
8 9
6 1
4 2
2 5
2 9
2 10
1 9
9 4
10 2
8 4
9 1
7 8
1 2
6 10
8 2
8 10
5 4
10 9
7 2
3 2
6 8
5 4
8 9
8 10
6 8
10 4
7 3
3 5
9 8
6 7
5 3
5 8
2 ...

output:

2 2 2 2 2 2 2 2 1 2

result:

ok answer = 18048

Test #13:

score: 0
Accepted
time: 812ms
memory: 321804kb

input:

18 15 22
8 17
13 14
5 15
2 17
18 1
17 10
1 5
6 18
1 6
11 2
15 17
2 13
4 3
1 10
16 14

output:

3 1 0 0 3 3 0 0 0 3 0 0 0 0 3 0 3 3

result:

ok answer = 25

Test #14:

score: 0
Accepted
time: 127ms
memory: 128300kb

input:

18 15 1
1 13
2 3
8 10
6 10
15 11
18 3
8 6
18 5
4 13
12 5
14 4
5 3
16 4
18 9
8 2

output:

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

result:

ok answer = 0

Test #15:

score: -100
Memory Limit Exceeded

input:

18 15 47
12 9
11 9
9 3
12 2
13 2
3 11
9 12
17 2
15 7
10 9
8 15
5 4
10 13
8 9
12 16

output:

0 7 7 0 0 0 0 0 7 6 7 7 6 0 0 0 0 0

result:
English 繁體中文 简体中文

Server Time: 2024-12-05 08:09:55 | OpenSource Project