ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#214129 | #2045. c | nullptr_qwq | 100 | 1227ms | 51752kb | C++11 | 1.8kb | 2024-11-15 18:46:52 | 2024-11-15 23:24:31 |
answer
// https://loj.ac/s/2069475
// 提交时间 2024/05/23 15:24:18
// Problem: #2509. 「AHOI / HNOI2018」排列
// Contest: LibreOJ
// URL: https://loj.ac/p/2509
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// Author: nullptr_qwq
//
// Powered by CP Editor (https://cpeditor.org)
// 私は猫です
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define ll long long
#define pb push_back
#define mkp make_pair
#define fi first
#define se second
#define inf 1e9
#define infll 1e18
#define pii pair<int,int>
#define F(i,a,b) for(int i=a;i<=(b);i++)
#define dF(i,a,b) for(int i=a;i>=(b);i--)
#define wh(lzm) while(lzm--)
#define cmh(sjy) while(sjy--)
#define lowbit(x) (x&(-x))
#define HH printf("\n")
#define eb emplace_back
using namespace std;
ll read(){
ll x=0,f=1; char c=getchar();
while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*f;
}
const int mod=998244353,maxn=500005;
vector<int>g[maxn];
int n,a[maxn],fa[maxn],sz[maxn];
ll w[maxn];
int find(int x){ return fa[x]==x?x:fa[x]=find(fa[x]); }
struct node{
int u,siz;
ll sum;
bool operator<(const node &rhs)const{ return 1ll*sum*rhs.siz>1ll*rhs.sum*siz; }
};
priority_queue<node>q;
void solve(){
n=read();
F(i,1,n) fa[i]=i;
F(i,1,n) g[a[i]=read()].push_back(i);
F(i,1,n) {
int x=find(a[i]),y=find(i);
if(x==y) return puts("-1"),void();
fa[x]=y;
}
F(i,0,n) fa[i]=i,sz[i]=1;
F(i,1,n) w[i]=read();
F(i,1,n) q.push((node){i,1,w[i]});
ll ans=0;
while(!q.empty()){
int u=q.top().u,siz=q.top().siz; q.pop();
if(sz[u=find(u)]!=siz) continue;
int p=find(a[u]);
ans+=1ll*w[u]*sz[p];
sz[p]+=sz[u],w[p]+=w[u],fa[u]=p;
if(p>0) q.push({p,sz[p],w[p]});
}
cout<<ans;
}
signed main(){
int sjy=1;
cmh(sjy) solve();
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 7ms
memory: 12912kb
input:
10 2 8 3 4 1 2 4 8 5 8 1 2 8 1 10 2 9 8 8 8
output:
-1
result:
ok "-1"
Test #2:
score: 10
Accepted
time: 0ms
memory: 12952kb
input:
10 0 9 5 5 0 0 0 0 0 0 576848570 9374579 447058478 375476508 17899037 890199416 691424702 96833317 4...
output:
27663373474
result:
ok "27663373474"
Test #3:
score: 10
Accepted
time: 3ms
memory: 12948kb
input:
15 0 0 0 12 6 0 0 14 8 0 0 7 6 15 0 1 4 7 1 5 1 1 6 8 6 1 1 2 6 2
output:
571
result:
ok "571"
Test #4:
score: 10
Accepted
time: 0ms
memory: 12948kb
input:
15 10 0 13 14 0 0 4 9 0 2 0 0 0 0 10 699156165 159021634 857055962 44497989 345951671 893758337 8465...
output:
78062614530
result:
ok "78062614530"
Test #5:
score: 10
Accepted
time: 0ms
memory: 13052kb
input:
1000 144 384 112 973 710 47 773 579 421 233 4 657 112 596 133 780 803 571 300 804 34 291 507 270 79 ...
output:
37419575
result:
ok "37419575"
Test #6:
score: 10
Accepted
time: 3ms
memory: 13048kb
input:
1000 349 415 281 956 749 201 628 217 723 900 513 106 618 978 176 448 834 704 763 266 466 533 192 379...
output:
370124146702558
result:
ok "370124146702558"
Test #7:
score: 10
Accepted
time: 72ms
memory: 21100kb
input:
100000 14420 84013 87193 82068 10374 79474 25939 9590 32198 3548 47938 85741 12568 14530 8858 60495 ...
output:
37283654934273540
result:
ok "37283654934273540"
Test #8:
score: 10
Accepted
time: 67ms
memory: 21104kb
input:
100000 26403 63914 61602 32321 29105 19251 73439 61190 72905 30337 25317 66634 83841 38470 96206 848...
output:
140620474524379753
result:
ok "140620474524379753"
Test #9:
score: 10
Accepted
time: 533ms
memory: 51752kb
input:
500000 331714 145478 6577 175958 171774 304559 166867 26414 92325 132061 8297 12915 470473 419957 48...
output:
4728510666048798028
result:
ok "4728510666048798028"
Test #10:
score: 10
Accepted
time: 542ms
memory: 50628kb
input:
500000 392409 161541 72825 120014 449034 320962 490925 62120 211235 236719 211792 410060 31166 20275...
output:
1604788177397380986
result:
ok "1604788177397380986"
Extra Test:
score: 0
Extra Test Passed