QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#385910 | #8539. Identity Theft | lifan | 100 ✓ | 62ms | 161516kb | C++14 | 2.2kb | 2024-04-11 09:56:17 | 2024-04-11 09:56:17 |
Judging History
answer
//
// clang-format off
#include<bits/extc++.h>
#define pb push_back
#define P make_pair
#define st first
#define nd second
#define bit(s,x) (((s)>>(x))&1)
#define pnp(s) __builtin_popcountll(s)
#define ctz(s) __builtin_ctzll(s)
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii; typedef pair<ll,int> pli; typedef pair<ll,ll> pll; typedef pair<int,ll> pil;
inline ll read(){
ll x=0,f=1,c=getchar();
while(c<'0'||c>'9')f=(c=='-'?-1:1),c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
const int mod=998244353;
inline int fp(int x,ll p=mod-2,int m=mod,int res=1){
for(;p;p>>=1){if(p&1)res=1ll*res*x%m;x=1ll*x*x%m;}
return res;
}
const int N=1e5+2;
const int M=1e6+2;
const int INF=0x3fffffff;
// clang-format on
int n;
string s;
int ans;
int son[M][2],tot=1;
int ed[M];
int cs[N];
inline void insert(){
int u=1;
for(int i=0;i<s.length();++i){
int d=s[i]-'0';
if(!son[u][d])son[u][d]=++tot;
u=son[u][d];
}
++ed[u];
}
struct Node{ int cst,v,t; };
bool operator <(Node A,Node B){return A.cst > B.cst;};
__gnu_pbds::priority_queue<Node,less<Node>,pairing_heap_tag>q[M];
inline void dfs(int u,int dep){
if(!u)return;
int t1=son[u][0],t2=son[u][1];
if(!t1 && !t2){
ans+=cs[ed[u]];
int t=__lg(ed[u])+1;
q[u].push({t+dep+1,(1<<t)-ed[u],t});
return ;
}
dfs(t1,dep+1),dfs(t2,dep+1);
q[u].join(q[t1]),q[u].join(q[t2]);
if(!t1 || !t2)q[u].push({1+dep,1,0});
while(ed[u]){
Node res=q[u].top();q[u].pop();
if(res.v>ed[u]){
res.v-=ed[u];
ans += (res.cst-dep)*ed[u];
ed[u]=0;
q[u].push(res);
continue;
}
ans += (res.cst-dep)*res.v;
ed[u]-=res.v;
res.cst += 1+(res.t==0);
res.v=1<<res.t;
++res.t;
q[u].push(res);
}
}
int main() {
//freopen("data.in", "r", stdin);
// freopen(".in","r",stdin);
// freopen("myans.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;++i)cin>>s,insert();
for(int i=2;i<N;++i)cs[i]=cs[i-1]+1+ceil(log2(i));
//for(int i=1;i<=tot;++i)ans+=cs[ed[i]];
dfs(1,0);
cout<<ans;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 4
Accepted
time: 4ms
memory: 27580kb
input:
3 1 1 1
output:
5
result:
ok single line: '5'
Test #2:
score: 4
Accepted
time: 6ms
memory: 27524kb
input:
3 1 11 111
output:
2
result:
ok single line: '2'
Test #3:
score: 4
Accepted
time: 4ms
memory: 27612kb
input:
3 1 1 11
output:
4
result:
ok single line: '4'
Test #4:
score: 4
Accepted
time: 4ms
memory: 27616kb
input:
5 0 01 0011 010 01
output:
6
result:
ok single line: '6'
Test #5:
score: 4
Accepted
time: 4ms
memory: 27488kb
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: 3ms
memory: 27612kb
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: 7ms
memory: 27556kb
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: 8ms
memory: 27628kb
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: 27560kb
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: 4ms
memory: 27664kb
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: 4ms
memory: 27596kb
input:
97 1000 01000011111100101011110100110110110111010111000000011001010001011111000111000000111100101110110101001001010100001111000011010001101101100100111110101001000010111000100111100110010100100110101010011001101110000010111000101000011101110111110100100000110111011110000010010100100000111001 101 0 1...
output:
315
result:
ok single line: '315'
Test #12:
score: 4
Accepted
time: 4ms
memory: 27620kb
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: 8ms
memory: 27536kb
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: 8ms
memory: 27572kb
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: 27404kb
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: 47ms
memory: 65308kb
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: 55ms
memory: 69968kb
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: 59ms
memory: 62452kb
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: 56ms
memory: 95844kb
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: 58ms
memory: 68112kb
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: 52ms
memory: 107940kb
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: 27ms
memory: 36496kb
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: 62ms
memory: 75380kb
input:
99979 1 0 00001101110101110111110111110000100111110111010100011111111111000001110000011011011001111111010110110000110011001111010011001010010001000010011111011001010100111110011101000101011010011001100111000100110001100100000001110111010111100100101101111111000101000000010000011100111011001000101100...
output:
1487815
result:
ok single line: '1487815'
Test #24:
score: 4
Accepted
time: 15ms
memory: 29996kb
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: 51ms
memory: 161516kb
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'