QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#811060#9802. Light Up the Gridrotcar07WA 13ms4192kbC++231.0kb2024-12-12 15:02:562024-12-12 15:03:05

Judging History

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

  • [2024-12-12 15:03:05]
  • 评测
  • 测评结果:WA
  • 用时:13ms
  • 内存:4192kb
  • [2024-12-12 15:02:56]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int a[4],f[1<<16];
constexpr pair<int,int> sk[]={{1,0},{2,0},{4,0},{8,0},{3,1},{12,1},{5,2},{10,2},{15,3}};
inline void solve(){
	int m=0;int msk=0;
	cin>>m;
	while(m--){
		char a,b,c,d;cin>>a>>b>>c>>d;
		msk|=1<<((a-'0')+(b-'0')*2+(c-'0')*4+(d-'0')*8);
	}
	cout<<f[msk]<<'\n';
}
int main(){
	std::ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t;cin>>t>>a[0]>>a[1]>>a[2]>>a[3];
	memset(f,0x3f,sizeof f);
	priority_queue<pair<int,int>> q;q.emplace(0,1<<15);f[1<<15]=0;
	while(!q.empty()){
		auto [dis,p]=q.top();q.pop();dis=-dis;
		if(f[p]!=dis) continue;
		vector<int> v;
		auto upd=[&](int to,int dis){if(f[to]>dis)f[to]=dis,q.emplace(-dis,to);};
		for(int j=0;j<16;j++) if(p>>j&1) v.push_back(j);
		for(auto [ff,y]:sk){
			int to=1<<15;
			for(int x:v) to|=1<<(x^ff);
			upd(to,dis+a[y]);
		}
	}
	for(int i=0;i<16;i++)
	for(int j=0;j<1<<16;j++)if(j>>i&1)f[j^1<<i]=min(f[j^1<<i],f[j]);
	f[1<<15]=2**min_element(a,a+4);
	while(t--) solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 13ms
memory: 4172kb

input:

2 1000 100 10 1
4
10
00

01
00

00
10

00
01
1
11
11

output:

1121
2

result:

ok 2 number(s): "1121 2"

Test #2:

score: 0
Accepted
time: 9ms
memory: 4000kb

input:

2 1 1 1 1
4
10
00

01
00

00
10

00
01
1
11
11

output:

5
2

result:

ok 2 number(s): "5 2"

Test #3:

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

input:

1 1000000 1000000 1000000 1000000
1
11
11

output:

2000000

result:

ok 1 number(s): "2000000"

Test #4:

score: -100
Wrong Answer
time: 13ms
memory: 3992kb

input:

10000 8 2 7 8
8
00
01

00
11

00
10

11
11

10
10

01
10

01
00

10
11
8
11
01

11
00

01
10

11
11

00
01

01
01

01
00

11
10
9
00
00

01
01

10
11

00
01

11
10

11
00

11
11

00
11

01
10
9
11
11

10
00

11
00

11
01

00
10

01
11

00
01

01
01

10
01
11
00
01

01
01

10
10

00
11

11
11

11
10
...

output:

32
30
34
34
40
36
41
38
40
37
34
42
34
37
37
31
29
35
39
40
38
36
40
34
25
34
34
38
34
31
32
37
34
36
37
40
40
34
37
34
29
35
35
36
42
35
35
34
38
34
37
29
38
38
36
37
43
36
41
30
40
39
33
33
34
36
34
34
42
40
34
32
28
34
32
37
34
39
34
37
32
36
30
30
32
34
38
40
34
36
40
39
34
36
34
25
36
40
36
34
...

result:

wrong answer 1st numbers differ - expected: '34', found: '32'