QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#314539#1193. Ambiguous EncodingOFforest_1273AC ✓4ms8156kbC++141.6kb2024-01-25 19:56:392024-01-25 19:56:40

Judging History

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

  • [2024-01-25 19:56:40]
  • 评测
  • 测评结果:AC
  • 用时:4ms
  • 内存:8156kb
  • [2024-01-25 19:56:39]
  • 提交

answer

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

#ifdef genshin
#include <experimental/iterator>
#endif
const int INF = 0x3F3F3F3F;
const int maxn = 16;
priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> Q;
int dis[maxn + 1][1 << maxn];
signed main() { ios::sync_with_stdio(0); cin.tie(0);
    int n;
    cin >> n;
    vector<pair<int, int>> num(n+1); // len, mask
    for(int i=1;i<=n;++i){
		string s;cin>>s;
        int x=0,len=0;
        for(char c:s)x|=(c&1)<<len,++len;
        num[i]={s.size(),x};
	}
    memset(dis, 0x3f, sizeof dis);
    for(int i=1;i<=n;++i)/*初始化*/
		for(int j=1;j<=n;++j){
			int len1=num[i].first,len2=num[j].first,val1=num[i].second,val2=num[j].second;
			if((len1==len2&&val1==val2)||len1<len2)continue;
			if((val1&((1<<len2)-1))!=val2)continue;
			int nxt_len=len1-len2,nxt_val=val1>>len2;
			if(dis[nxt_len][nxt_val]>len1)dis[nxt_len][nxt_val]=len1,Q.push({len1,nxt_len,nxt_val});
		}
	while(!Q.empty()){
		auto [d,len,val]=Q.top();Q.pop();
		if(d>dis[len][val])continue;
		for(int i=1;i<=n;++i){
			int len2=num[i].first,val2=num[i].second,nxt_len,nxt_val,flag=0;
			if(len>=len2&&((val&((1<<len2)-1))==val2))nxt_len=len-len2,nxt_val=val>>len2,flag=1;
			else if(len<len2&&(val2&((1<<len)-1))==val)nxt_len=len2-len,nxt_val=val2>>len,flag=1;
			if(!flag)continue;
			int cost=max(0,len2-len);
			if(d+cost<dis[nxt_len][nxt_val])dis[nxt_len][nxt_val]=d+cost,Q.push({d+cost,nxt_len,nxt_val});
		}
	}
    if (dis[0][0] == INF)
        cout << "0\n";
    else
        cout << dis[0][0] << '\n';
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 8132kb

input:

3
0
01
10

output:

3

result:

ok answer is '3'

Test #2:

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

input:

3
00
01
1

output:

0

result:

ok answer is '0'

Test #3:

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

input:

3
00
10
1

output:

0

result:

ok answer is '0'

Test #4:

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

input:

10
1001
1011
01000
00011
01011
1010
00100
10011
11110
0110

output:

13

result:

ok answer is '13'

Test #5:

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

input:

3
1101
1
10

output:

4

result:

ok answer is '4'

Test #6:

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

input:

100
1010011110001
00000100010101
011010100100001
11100001100011
10010001010
1110001110110011
01001100111
1010100110010100
00000100111010
100111001100101
0010000000010
0111110011100110
0100111000001
1100101111110001
1100100110001
10100011010
10100000011000
1111001111001110
000000000101011
10101111011...

output:

102

result:

ok answer is '102'

Test #7:

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

input:

10
0110
001100
0100
0001
100
001010
0010
100010
1100
11101

output:

10

result:

ok answer is '10'

Test #8:

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

input:

10
1001
10111
11011
00010
001
001100
110
01110
111101
11100

output:

10

result:

ok answer is '10'

Test #9:

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

input:

10
0001
0101
1001
101
0010
010
00000
1000
00001
111101

output:

10

result:

ok answer is '10'

Test #10:

score: 0
Accepted
time: 1ms
memory: 8100kb

input:

100
0100001001101111
00001000100011
001111100110101
1010001010001
01110010101011
1110101100011
00100000100110
01111110100
110001111010
10101010001
00010000100100
00010011100
01101001100010
010111010101
00101110101001
00110100110110
00111001101
0001110011000011
11101100110
101111001011001
00101110100...

output:

110

result:

ok answer is '110'

Test #11:

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

input:

100
010110000010110
111001111001
00000010100111
1011000100011100
1010110100001000
0101110010110
11101010001
0001101001001101
10011111110010
01010001101
11011101010
011011111011001
111000111110
01011100011
0000111110110
000110001011
110100011000
10010011011
0011001010001
1010001110000110
100100100001...

output:

113

result:

ok answer is '113'

Test #12:

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

input:

10
011
011000
111011
0101
101000
010100
1101
10100
11111
001001

output:

11

result:

ok answer is '11'

Test #13:

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

input:

10
101
110
00000
100011
010
110001
001001
1110
011111
01001

output:

11

result:

ok answer is '11'

Test #14:

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

input:

200
100101110111000
0111100000111
1010110010001110
000001000000
111000100101
111010000110100
11100110010100
100110111110
1000100110110
0100010010111
001100010101
100001001110100
1110000011001111
0110100100100
111111111110
1110111010110
1101101000111
0001101001110001
000010110111110
101100110010
1010...

output:

116

result:

ok answer is '116'

Test #15:

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

input:

5
1
01
10101010101
10111000000
10000000101

output:

11

result:

ok answer is '11'

Test #16:

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

input:

100
000010101110
10101111011110
10000000001
001101011110101
110001010100
11110111011
0101101111010001
101010001101011
100001110100
100010110011000
1000001001101001
0011100110101
011110111100010
0100101100010
10001101011
011110010101011
0011001001000
0100001010100
11110110011
011101001011
01101011011...

output:

118

result:

ok answer is '118'

Test #17:

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

input:

10
01100
100
00101
0100
1110
11101
1010
01001
000101
10101

output:

12

result:

ok answer is '12'

Test #18:

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

input:

500
0110100111
10110100011100
100011111010111
010010111
0011100001101
10011001101101
0110010011
0101100
1000010111011
01110010110
111001111000
0110100010101
011001100100101
001000110001100
110100000101
100101100101111
0101111111110
00101001000010
1101100
0110000000
00011100000
1110010101
00000100010...

output:

14

result:

ok answer is '14'

Test #19:

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

input:

200
01100101110110
001100111001
1011000110000
101010101010
001000111100010
0010001111110011
010001010101000
010001001001000
1110100000100100
10001011011011
10001000010000
101101001101101
1100010011001001
10010100010100
00001001000111
0100000010011000
111000010100
000101001010000
000100100110101
0010...

output:

145

result:

ok answer is '145'

Test #20:

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

input:

10
1000
00001
01011
001001
110010
11000
110
01010
000001
01100

output:

14

result:

ok answer is '14'

Test #21:

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

input:

10
10111
1100
11011
001
0101
001000
00101
11101
100000
0111

output:

14

result:

ok answer is '14'

Test #22:

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

input:

200
1010111001101110
01010011010100
0111000011011
10000110011100
110110111010100
100001111010001
1110001100001
10001000011101
0001000110011010
1111110000000000
1001000110111001
101011110110111
1101011100010
100001000110
000001011001
011001111111
111101111101000
11101011100010
001011010101000
0001001...

output:

156

result:

ok answer is '156'

Test #23:

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

input:

10
1010
011010
010001
0101
001001
101000
011
111
10010
110

output:

17

result:

ok answer is '17'

Test #24:

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

input:

200
1111100000000
0011100001011100
00000000000111
1100101001111
100100010110111
11001111101011
1100101101101001
100001101010110
01001111000100
001111111001011
011111010101
0011000101010
0110010000000111
110101000110
1110101110011011
1101110010011
0010111101011010
1111010011010
11001000110001
0010010...

output:

188

result:

ok answer is '188'

Test #25:

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

input:

10
000
110100
0111
010
101
11100
010100
00110
011000
010111

output:

18

result:

ok answer is '18'

Test #26:

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

input:

200
1110101101
10111111001
1000011110
1111110011011
01100100101110
010001111000110
1010111010
1000110011010000
11100011110001
11000100001
1011101110011000
000110110000010
111111011000011
0110010000001
10001000101
1101010000
1000000001
1101000010000
01110101110
00000101111
0100111011110
0110110011011...

output:

0

result:

ok answer is '0'

Test #27:

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

input:

200
101010110010
1001001001000111
0010011011011101
1111100000111110
11101010011
10100001001001
000100000000
010011000001011
1100010110010011
11101101110
110001010001
00000111000
011010101001001
10011110110111
0111001111000
110111111010011
1000000110000101
01100101110
00011100011
0111001001111011
101...

output:

0

result:

ok answer is '0'

Test #28:

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

input:

1000
01000110
11101111
0100011000101111
0010111110011101
1001110111010001
1101000101110010
0111001000110101
0011010110001010
1000101011101011
1110101110111110
1011111001111101
0111110111110100
1111010001111100
0111110001000001
0100000100101010
0010101011010100
1101010001000010
0100001010010011
10010...

output:

2048

result:

ok answer is '2048'

Test #29:

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

input:

200
11001100000000
1010101001010
0111110011100010
111011011001000
0110111110010
111010010100010
0100111000001010
0001110101000010
00000100001101
01110010111001
000001100110000
1111011001000
10001110101100
111000011010110
10110110010001
11000101111010
1100000010011
000011010000001
11111011011110
1100...

output:

231

result:

ok answer is '231'

Test #30:

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

input:

200
10100110111100
101000100111101
0110111110110000
111110000001110
1001011001111101
001111001101111
00111101101111
01010100000100
111001100000001
1100001111011001
0110101010001
001101000011101
0000101111000101
11100110101010
00011111011001
1001010000111
000111100111110
0111111101001
011000101111001...

output:

283

result:

ok answer is '283'

Test #31:

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

input:

200
111101000110010
01001010110010
100010011011010
0101101110000
00101000111011
1010111110101
01111010011110
100011111110000
10000011100111
0111000010000111
001001011000011
0000100110011000
11100011110001
10111110110000
001100110100011
1101111011011
000100111100111
10010011100010
0011001010011
00001...

output:

350

result:

ok answer is '350'

Test #32:

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

input:

200
11000010000111
11110111011011
00100011011100
1101000001011
01100001110101
000111101010111
1011110100001011
0011110000011
0100011011001
01000101000000
00111111110110
111100011010001
100101111001100
1011101110111
1110110010000
1001011010001
1010111100001001
110001010111000
1011100001000
1010010001...

output:

359

result:

ok answer is '359'

Test #33:

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

input:

100
01101111110001
101000110111
11111011011
00000011010
0000101010001
010001100110
1110010000101
100101100011000
01100000100
1101111010011010
101110101100
101001110101001
00000011110
01000011010
011100110101111
10011010110
000000101100110
10100100011110
001010101001100
11111110000
10001001101010
100...

output:

36

result:

ok answer is '36'

Test #34:

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

input:

200
0111100011111000
0100111110000
010111111011111
1011011000001111
00100111001000
10111000101110
0110010001000011
01010011001011
11010011111110
0110010000010110
0101100001011
011011011100100
0011101110010110
1110010000001
001111010111110
1110011010100
111001000000111
001000100100001
1010101101110
1...

output:

367

result:

ok answer is '367'

Test #35:

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

input:

100
000001010010010
00100000011
0011001000001101
1011110011001
111010010100010
011001000100000
000101100001
110110100111
0011100011111111
1110010111010
10111001011111
101010011001
1011100100101101
0110001000110000
111010100010
010000111110
10010100011
01000011001000
1010101100101
000111111111
011001...

output:

37

result:

ok answer is '37'

Test #36:

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

input:

100
1011001001010101
000010011000001
1101101010101
110111101101
01110100100000
11111101010
0001010011011
111101110110001
110000100110011
111101110111
0100001101010
011101100111000
1001100001101000
1001100000000
11100011100
10100110110110
0011000110110000
1111111010010100
10001001001
0000001100001110...

output:

38

result:

ok answer is '38'

Test #37:

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

input:

200
00100010100101
011111101101000
0010100111101111
001101100000001
1111111001111
1101111110001
000000100010100
11100010110101
011011011001110
00000111010101
1100110110100101
0100010110011
1101011000111011
111000111100110
111010100001010
1011010001100001
0000110011000
1011101100101110
10111001101001...

output:

391

result:

ok answer is '391'

Test #38:

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

input:

100
0011010101100
0111110100111
11001110010
111011111111100
001000010110110
00010010000
1001010011110
100101101110
0010100110001000
1110100001101000
111111110101001
10000010011010
11111110001101
1000000110011101
111011000001100
00110101101
110101110001
0001110001101001
000000111001
1111100101000
010...

output:

39

result:

ok answer is '39'

Test #39:

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

input:

200
00000000110010
1010111101010
010101010110101
01011010001111
011000101010001
11111011001101
1110001100000
110110111111110
0000010110001
1011011111101000
1010010011010
0111111011001101
0101110110111010
1100110101010
0000100100110100
010110010100010
1001011111011
1110011001100
1111101001101
1010110...

output:

421

result:

ok answer is '421'

Test #40:

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

input:

200
100001111000011
11100101100101
101001101110011
0100000001010000
011010000100010
010000110001110
00011110001001
000111010011001
0010000010101
0010110011011
0101111010111
0100010011100100
101010000111011
01100110010101
1111000000110011
01101010000111
010000001001011
0011101101011
10000110110100
11...

output:

445

result:

ok answer is '445'

Test #41:

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

input:

100
0100100110110101
101000011011
111011000101000
11111001000
1101011111111
0000010011010110
10100001110
01111000100
101101011011000
1110011110100110
1100101111010110
10011011000011
0010111001110101
1001010111110110
11000110001100
00011010111100
111011000111
010000010111
11111111100000
1010011100110...

output:

47

result:

ok answer is '47'

Test #42:

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

input:

100
1111000001010
1000011001010
001011111010
010101100100
1111000101101001
101010011100
1100010000010111
11100011001100
1011111100011100
000001100000
00101111101
001010111010
0001010110101100
0010011110100010
111100000000111
010000100101
001011000010101
001110001000
011101001101000
000001110000010
0...

output:

48

result:

ok answer is '48'

Test #43:

score: 0
Accepted
time: 1ms
memory: 8156kb

input:

100
00101001011
1010000111111
01101101010101
110001101010000
00000011101010
0010100101101111
01101101010011
11111001111
0101001000011111
1101000001101
010011001001011
01001101011111
10010111101110
110101001110001
100010011000
000101101010
0000111010111
11110011010
10010101110
001001110111011
0101010...

output:

49

result:

ok answer is '49'

Test #44:

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

input:

500
101011100001100
0001100110110110
0001111101110000
11010000110111
110110001011110
011011011001011
101001011101001
1001111010100
10001101110110
00110001000011
1011110011100
001010000110011
01100110011110
01000111010011
01100010010001
0110000110101
01001010111001
00001100010010
0001110010111001
110...

output:

0

result:

ok answer is '0'

Test #45:

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

input:

100
10101111001
000010111001
10001000001
01101000011100
0001001101100011
00000011110
10010111011
01011001011
011111101101001
0000000000000
101100010111
0010111100110011
1101101110110011
0001010011100000
110010111011
1110110010000010
11010111010111
10001000011
0010101110110100
000100111001110
1100111...

output:

51

result:

ok answer is '51'

Test #46:

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

input:

100
111111001011
011011000011
1100010001000000
10110101001
0011000100100
0100000101010000
0000110110001
10110001011
01100011110
010010110111
00110001110
0100000110100
111101111111111
10000111010
110100110001011
0111011101001
010000010001
01011101110101
1000101100101
10000110111
001100011001110
01000...

output:

52

result:

ok answer is '52'

Test #47:

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

input:

100
10111101000100
11000000100
010111000100000
11011010101
0000000101100001
111100001111000
01010001001
11001011011
1101001110010001
0010100111110101
1001011110110
01010111010
011010101111
0100000010011
100001110111011
101110111100010
11001001000
000000011101110
1011100010110010
0001101011011
110011...

output:

54

result:

ok answer is '54'

Test #48:

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

input:

100
1100100101000
01011000111010
010101101011000
1010011101110111
1010010011011000
11001001010101
00010011010
110110001001101
10011111110111
10101110000
1010110001111
0110010100000100
100100100001
011101000101
0110010001001110
100100001001110
00100010011011
1011101010010
0101100010111
11000101011110...

output:

55

result:

ok answer is '55'

Test #49:

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

input:

100
0011010101001011
111010010100000
11001010101
01110011100000
00111110000011
0111000101001
011011100001
1011101010110011
0011010000000
1111001100000
10101110000
000001101010101
0100010000111
011000010101
00011100101101
0010011011110001
01111110001111
01100111010
011101001011001
11011001010000
0110...

output:

59

result:

ok answer is '59'

Test #50:

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

input:

3
1101
1
10

output:

4

result:

ok answer is '4'

Test #51:

score: 0
Accepted
time: 1ms
memory: 7860kb

input:

100
1000000010110000
1010110000101101
11001011110100
100101100101
110100110110100
0110000100111110
101110101110
1010101000110
1011000101100
0001001110001100
11000111010
1110011100010
00010110110011
10100010100
00010011011011
10101011111101
000001010101101
0111111001010011
01110111101
00101110100
100...

output:

61

result:

ok answer is '61'

Test #52:

score: 0
Accepted
time: 1ms
memory: 8072kb

input:

100
110000101000110
1000111101010101
100001101101
10100101101
01101010101101
11111110101
0111010101111001
011001001000
0111011000010
1101100101010
01111110101100
10111000010
0000111100001
001011010100
1010111101000
11111110110010
0101101001010100
10111010001011
01110100011100
0001110011111010
011010...

output:

62

result:

ok answer is '62'

Test #53:

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

input:

5
01000100111
01
000100111
010101
01010101

output:

6

result:

ok answer is '6'

Test #54:

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

input:

67
1
1111111111111110
0111111111111100
0011111111111000
0001111111111000
0001111111111010
0101111111110000
0000111111110010
0010111111110100
0100111111110110
0110111111100000
0000011111100010
0001011111100100
0010011111100110
0011011111101000
0100011111101010
0101011111101100
0110011111101110
011101...

output:

654

result:

ok answer is '654'

Test #55:

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

input:

100
00000101101
10000010111
010000101111
111011101101100
111110100101
100000000010100
011111111110
010011110011010
01110001111
011011000000011
100011110110100
001011111101101
100010110000
11110000110101
0011001011110
110110111101000
0001000110001
000100101101
00101010110
1101111001001100
01110111100...

output:

67

result:

ok answer is '67'

Test #56:

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

input:

100
1000111110000111
10100111010
01000010011110
000100110100000
0111100111001101
1011110000111011
11101001010010
01001110010010
110010110001
00011111001
11110100100110
1110111110010110
1110000101011110
1001010100000
1111100100110
00000100001011
000000011110
10000000010
10001001000000
010010010111010...

output:

68

result:

ok answer is '68'

Test #57:

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

input:

10
1100
100
000
01111
111
1110
10011
101
110
0101

output:

7

result:

ok answer is '7'

Test #58:

score: 0
Accepted
time: 1ms
memory: 7876kb

input:

100
0010100010100101
00000111111010
1000001110111
10101000110
010100100011
0110001011001
11111110001
000000110110110
1010001011010
10011000011
0111101100110101
1111100100000100
011011010011
00001011100
1001000101001001
111011111010111
01001010001
110001000111
1100001110001
001011111001
11000101000
1...

output:

80

result:

ok answer is '80'

Test #59:

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

input:

100
0000010010101100
110011111110
0110001100111
000100001001
1001011100111101
00101100001100
11011101001011
11000110011
00111001011
0101011100111
1100001101100101
01100100101
0110000110100000
01011010101
1000110010010
11011111011011
001000111110
111000101000
01101110110011
0010010011001111
110100001...

output:

83

result:

ok answer is '83'

Test #60:

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

input:

10
11001
11000
1111
1010
001
10011
1011
01011
100
01110

output:

8

result:

ok answer is '8'

Test #61:

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

input:

4
00010101
000
10
1

output:

8

result:

ok answer is '8'

Test #62:

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

input:

10
001
110
010110
00111
101100
001011
1011
111
10101
0000

output:

9

result:

ok answer is '9'

Test #63:

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

input:

10
011
111111
010
1101
00101
11010
110000
00011
1001
001

output:

9

result:

ok answer is '9'