QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#386056#8539. Identity Theftlifan100 ✓42ms70928kbC++142.2kb2024-04-11 11:26:552024-04-11 11:26:56

Judging History

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

  • [2024-04-11 11:26:56]
  • 评测
  • 测评结果:100
  • 用时:42ms
  • 内存:70928kb
  • [2024-04-11 11:26:55]
  • 提交

answer

// 
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#define ls trie[x][0]
#define rs trie[x][1]
#define LL long long
#define pr pair <LL, int>
#define mr make_pair
using namespace std;
const int MAXN = 1e7 + 5;
char s[MAXN];
int n, tot = 1, trie[MAXN][2], flg[MAXN], dp[MAXN], F[MAXN], ans;
void read(int &x) {
	x = 0; bool f = 1; char c = getchar();
	for(; c < '0' || c > '9'; c = getchar()) if(c == '-') f = 0;
	for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
	x = (f ? x : -x);
}
void ins() {
    int len = strlen(s + 1); int now = 1;
    for(int i = 1; i <= len; i ++) {
        int q = s[i] - '0';
        if(!trie[now][q]) trie[now][q] = ++ tot;
        now = trie[now][q];
    }
    flg[now] ++;
}
void update(int x) {
    if(flg[x] == 1 && !ls && !rs) {
        dp[x] = 3; return;
    }
    if(ls && rs) {
        dp[x] = min(dp[ls], dp[rs]) + 1;
        if(dp[ls] < dp[rs]) F[x] = 0;
        else F[x] = 1;
    }
    else if(!ls) dp[x] = 2, F[x] = 0;
    else dp[x] = 2, F[x] = 1;
}
int Move(int x) {
    if(flg[x] == 1 && !ls && !rs) {
        flg[x] = 0; ls = ++ tot; rs = ++ tot; flg[ls] = 1; flg[rs] = 1;
        dp[ls] = 3; dp[rs] = 3; dp[x] = 4;
        return 3;
    }
    if(ls && rs) {
        int t;
        if(F[x] == 0) t = Move(ls) + 1;
        else t = Move(rs) + 1;
        update(x); return t;
    }
    if(!ls) {
        ls = ++ tot; flg[tot] = 1; dp[ls] = 3; update(x); return 2;
    }
    rs = ++ tot; flg[tot] = 1; dp[rs] = 3; update(x); return 2;
}
void dfs(int x) {
    if(x == 0) return;
    dfs(ls); dfs(rs); update(x);
    if(flg[x] == 1 && ls == 0 && rs == 0) return;
    if(flg[x]) {
        for(int i = 1; i <= flg[x]; i ++) {
            int t = Move(x); //printf("|%d|", t);
            ans += t - 1;
        }
    }
}
int main() {
    // freopen("A.txt", "r", stdin);
    // freopen("B.txt", "w", stdout);
    read(n);
    for(int i = 1; i <= n; i ++) {
        scanf("%s", s + 1); ins();
    }
    dfs(1); printf("%d", ans);
    return 0;
}
/*
g++ -o IdentityTheftP IdentityTheftP.cpp -std=c++14 -O2 -fno-ms-extensions -Wconversion -Wshadow
./IdentityTheftP
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 4
Accepted
time: 1ms
memory: 7760kb

input:

3
1
1
1

output:

5

result:

ok single line: '5'

Test #2:

score: 4
Accepted
time: 1ms
memory: 7736kb

input:

3
1
11
111

output:

2

result:

ok single line: '2'

Test #3:

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

input:

3
1
1
11

output:

4

result:

ok single line: '4'

Test #4:

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

input:

5
0
01
0011
010
01

output:

6

result:

ok single line: '6'

Test #5:

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

input:

14
0
1
1
0
1
0
1
1
1
1
1
0
0
1

output:

41

result:

ok single line: '41'

Test #6:

score: 4
Accepted
time: 7ms
memory: 12800kb

input:

100000
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1...

output:

1668928

result:

ok single line: '1668928'

Test #7:

score: 4
Accepted
time: 13ms
memory: 10816kb

input:

100000
1
0
1
0
1
0
1
0
1
1
1
1
1
1
0
1
1
1
1
1
1
1
0
1
1
0
1
1
1
0
0
1
1
1
1
0
0
0
0
1
0
0
0
1
0
1
0
0
0
1
1
1
0
0
1
0
0
1
0
1
0
1
0
1
0
0
0
1
1
1
0
1
0
1
1
1
0
1
0
1
0
0
0
1
1
0
1
0
0
0
0
0
0
0
0
0
1
0
1
1
0
0
0
1
1
0
0
0
1
0
0
0
1
1
1
0
0
1
1
1
1
1
0
0
1
1
1
1
1
1
0
1
0
1
1
0
1
1
1
0
1
1
1
1
0
0
1...

output:

1568928

result:

ok single line: '1568928'

Test #8:

score: 4
Accepted
time: 1ms
memory: 7808kb

input:

98
11101
111101
0
1
11
111101
11
1
11
010
1
1
111101
101101000
010
11111001111101010010001010110101100110001110100111011011010010010000010110111001110001000000000110101010011111101010101000001111000100101011011000000001001101000001011111001001111111011000111100111100001101011001111000111111100110110...

output:

351

result:

ok single line: '351'

Test #9:

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

input:

99
01
1000
00
1000
0
1
1
0
1
0100110111101101010000111
11011010001000010101001111000111011011001101001110110101100101101011011000110001010000101111
0111000000110010001110
01100100100000010110000001010111001100001000111001100001010001001110001100000001001
0
1
00
1000
1
00
00
00
111
00
00
1
0
10100001...

output:

353

result:

ok single line: '353'

Test #10:

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

input:

98
011
1101
1
1001101
011
0
10
0
1
011001000000110111101
100110101111100
1
0
1101010011010
0100
1
000
101011100101001001111111100011000
00100100111010001011
1000101011111001111100111110
001000000111
1101
011
1
1
000
1
1
011
000
1
0
0100101111100011
011
0
1
00110
1
1
1010111100001001000000011010
011
...

output:

362

result:

ok single line: '362'

Test #11:

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

input:

97
1000
01000011111100101011110100110110110111010111000000011001010001011111000111000000111100101110110101001001010100001111000011010001101101100100111110101001000010111000100111100110010100100110101010011001101110000010111000101000011101110111110100100000110111011110000010010100100000111001
101
0
1...

output:

315

result:

ok single line: '315'

Test #12:

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

input:

96
1100110
10
1100110
1100110
11010
00
0010100
00110
000
100101
0010100
0
10110
110
11010
10110
11010
110110111110011100101011011111010101101011110101110100101110011100001001111111001110010000000011101100010100110100110010001011110111000111101001100011101101100101000101100011000011010111000010011101...

output:

284

result:

ok single line: '284'

Test #13:

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

input:

96
0
0011010001010
0111110
11111
1
1011011101
0011001010
0111110110000101000
1001101110100001100001100011111001011100111
101000
01010100
111001000001010111110101111101111010100
01
101000
101000
101000
0
101000
000100000111010001100011110000111010111111001010011
01110
110010001110001100011100011111
0...

output:

206

result:

ok single line: '206'

Test #14:

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

input:

99
01
1
0
10110011001
01
00011
11010
0011011010011110101001110
0
1
110
0
0100010101101
0
0
00011
000010000010001001
0
110
0
11010
0
11010
1
1
0
0
1
010101010110101100000
1
11010
11010
111110
1
0
1
11010
01
0001011101
110
1010000000011000110001110010101001011010100000101000110101100001010010010010100...

output:

384

result:

ok single line: '384'

Test #15:

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

input:

95
00010000010110101000
110001
0111111001
0
00000100111000110111
01101100100010001111001
010001
100100101010010111010000100110000000100101000100100010
10
010001
101100100111100001100111010001000000
01001111
10
0
0
00011101000010110100111110000101010100010101001011011101011100000110101111100000100100...

output:

232

result:

ok single line: '232'

Test #16:

score: 4
Accepted
time: 33ms
memory: 23248kb

input:

99503
0
1
1
0
1
0
010101000110111001
01110000010001
1
110
1
0
1
0
1
0
0
0
110110100
1
11111
1
110
0
1100101100110
1110001010001001010000001110
0
1
11110010001110001001111001001000010101101011101
1
110000001011000100001110111011011
0
0
0
0
110
1
1
1
0
10110110110011110101111000000101100010110100101
0...

output:

1284449

result:

ok single line: '1284449'

Test #17:

score: 4
Accepted
time: 36ms
memory: 24544kb

input:

99814
0
0
1
1
1
0
0
1
00
0
0
1
0
0
0
0
1
0
1
1
0001001101001111011101001111110000000100100101001011111111001011
01110010011101100
1
1
1
0
0
1
0
0
000100110
0
1
0
10011111101110111100001
1
1
1
0
1
1
1111001011011101011011100
1
1
111010010001100100010010000011101110100111000101000111110000001101010111...

output:

1383883

result:

ok single line: '1383883'

Test #18:

score: 4
Accepted
time: 32ms
memory: 23788kb

input:

99182
11101000100110111001111000111000101100
0
0
0
01000111000101100100110101111
1
1
0
1
1
0111111111111000011
0
0
0
1
0001100111000100000
1
0001000101110110011111111001010100
0100010101100101000011001010110011000110101110010010100001100000001101011000000000101010011100111011001110000101001100000101...

output:

1222291

result:

ok single line: '1222291'

Test #19:

score: 4
Accepted
time: 21ms
memory: 39712kb

input:

95541
1
0
0101
1000
01011111001000100
11001010111100
0111101111
1
0
1
111011
1
1
1
0
10110011
0001
1001
001
1
1
0100
010101100100110110
1
1
000
0
111011
1010001000111010010101
0101011001
001000110000000
01011111001000100
01010
01010
1
01011111001000100
1
1
0
1
00000101
1
011111100101110100101
1
0001...

output:

1157073

result:

ok single line: '1157073'

Test #20:

score: 4
Accepted
time: 30ms
memory: 22032kb

input:

99762
1
1
1
0
101111000010000010101
1
1
0
1
0
0
1
0
0
0100101111110100001011011100100000010000011111100000110001101001010011011111011011000
010100001000111011011100000110010110010
0
000001110
000100010011100110111110010001010011010100101100101100101001010101111001001101111000111010101011001110
1
0
0...

output:

1336194

result:

ok single line: '1336194'

Test #21:

score: 4
Accepted
time: 20ms
memory: 43180kb

input:

98138
00011110110110100011111010010001
1
1
011101101100001110100000001
0
1
1
1
0
00101101010100010110010010001100011010100
11
1
1
1
1
1
0
1
1
11
00110
01011001100000000111100001000011010100
1
1
000011001
1
0
1
1
10001010000
11001100000101011
11011101111
0010100001010
1
0
1
0
011001010100001101100010...

output:

1259135

result:

ok single line: '1259135'

Test #22:

score: 4
Accepted
time: 20ms
memory: 12480kb

input:

96020
010111010010000
011000110110
11111
000011001011000
110
0101111001000
1
001010100100
011000110110
0011100
00
10
001010100100
001111
11
1
0101100110110001
001000011
0
011000110110
11100100100
0011100
00
111111101100011010
1
0011100
00011011
1111000011
00011001
1101010001110
010111010010000
01011...

output:

1032640

result:

ok single line: '1032640'

Test #23:

score: 4
Accepted
time: 27ms
memory: 26420kb

input:

99979
1
0
00001101110101110111110111110000100111110111010100011111111111000001110000011011011001111111010110110000110011001111010011001010010001000010011111011001010100111110011101000101011010011001100111000100110001100100000001110111010111100100101101111111000101000000010000011100111011001000101100...

output:

1487815

result:

ok single line: '1487815'

Test #24:

score: 4
Accepted
time: 9ms
memory: 10612kb

input:

70689
101001011101101
11111000
111110101111110
01011001001
001011000100011
011100101010001
0011110001101
010010000000011
11110110101100
101000110011100
101101011001100
011101011010111
10011000111111
1110101000111
1100100011010
0000001101110000
011110100001000
110011000011011
0111110100111
0000000000...

output:

141345

result:

ok single line: '141345'

Test #25:

score: 4
Accepted
time: 42ms
memory: 70928kb

input:

100000
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1...

output:

1668911

result:

ok single line: '1668911'