QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#734449 | #8237. Sugar Sweet II | WorldFinalEscaped | WA | 251ms | 79884kb | C++14 | 3.5kb | 2024-11-11 10:47:06 | 2024-11-11 10:47:07 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> Pair;
const int N=5e5+5,mod=1e9+7;
#define F first
#define S second
int a[N],b[N],w[N],fac[N],Inv[N];
int vis[N],inl[N],pos[N];
int siz[N],fa[N],dep[N],top[N],son[N];
int T,n,cnt;
set<Pair> s1[N],s2[N];
vector<int> G[N];
inline int fastpow(int x, int y){
int z=1;
for (; y; y>>=1,x=1ll*x*x%mod)
if (y&1) z=1ll*z*x%mod;
return z;
}
void dfs1(int u, int f){
dep[u]=dep[f]+1,siz[u]=1,fa[u]=f;
for (int v:G[u]){
dfs1(v,u);
if (siz[v]>siz[son[u]]) son[u]=v;
}
}
void dfs2(int u, int st){
top[u]=st;
if (son[u]) dfs2(son[u],st);
for (int v:G[u])
if (!top[v]) dfs2(v,v);
}
inline void Ins(int i){
if (inl[i]) s2[pos[i]].insert({inl[i],i});
else s1[top[i]].insert({dep[i],i});
}
inline void Del(int i){
if (inl[i]) s2[pos[i]].erase({inl[i],i});
else s1[top[i]].erase({dep[i],i});
}
inline Pair query_loop(int x){
if (s2[pos[x]].empty()) return {-1,-1};
auto it=s2[pos[x]].lower_bound({inl[x],0});
if (it!=s2[pos[x]].end()) return {(*it).F-inl[x]+1,(*it).S};
return {(*s2[pos[x]].begin()).F+s2[pos[x]].size()-inl[x]+1,(*s2[pos[x]].begin()).S};
}
inline Pair query(int x){
if (inl[x]) return query_loop(x);
int rt=0;
for (int i=x; i; i=fa[top[i]]){
// if (i==2) printf("=-=-=>%d\n",i);
auto it=s1[top[i]].upper_bound({dep[i],n+1});
if (it!=s1[top[i]].begin()){
it--;
return {dep[x]-(*it).F+1,(*it).S};
}
if (fa[top[i]]==0) rt=top[i];
}
Pair ret=query_loop(rt);
if (ret.F==-1) return ret;
return {ret.F+dep[x]-1,ret.S};
}
int main(){
fac[0]=Inv[0]=1;
for (int i=1; i<=500000; i++) Inv[i]=fastpow(fac[i]=1ll*fac[i-1]*i%mod,mod-2);
for (cin>>T; T; T--){
scanf("%d",&n); cnt=0;
for (int i=1; i<=n; i++) scanf("%d",&a[i]);
for (int i=1; i<=n; i++) scanf("%d",&b[i]);
for (int i=1; i<=n; i++) scanf("%d",&w[i]);
for (int i=1; i<=n; i++){
if (vis[i]) continue;
int cur=i;
for (; !vis[cur]; cur=b[cur]) vis[cur]=i;
if (vis[cur]!=i) continue;
cnt++;
for (int j=1; !inl[cur]; cur=b[cur],j++) inl[cur]=j,pos[cur]=cnt;
}
for (int i=1; i<=n; i++)
if (!inl[i]) G[b[i]].push_back(i);
for (int i=1; i<=n; i++)
if (inl[i]){
dfs1(i,0);
dfs2(i,i);
}
for (int i=1; i<=n; i++){
// if (a[i]<a[b[i]]) printf("A: %d\n",i);
// if (a[i]>=a[b[i]]+w[b[i]]) printf("B: %d\n",i);
if (a[i]<a[b[i]] || a[i]>=a[b[i]]+w[b[i]]) Ins(i);
}
for (int i=1; i<=n; i++){
Pair d=query(i);
// printf("-->%d %d %d\n",i,d.F,d.S);
if (d.F==-1 || a[d.S]>=a[b[d.S]]+w[b[d.S]]) printf("%d ",a[i]);
else printf("%d ",(a[i]+1ll*w[i]*Inv[d.F])%mod);
}
puts("");
/*
int a[N],b[N],w[N],fac[N],Inv[N];
int vis[N],inl[N],pos[N];
int siz[N],fa[N],dep[N],top[N],son[N];
int T,n,cnt;
set<int> s1[N],s2[N];
vector<int> G[N];
*/
for (int i=1; i<=n; i++){
s1[i].clear(),s2[i].clear(),G[i].clear();
a[i]=b[i]=w[i]=0;
vis[i]=inl[i]=pos[i]=0;
siz[i]=fa[i]=dep[i]=top[i]=son[i]=0;
}
}
}
/*
1
5
2 1 3 2 1
5 1 1 3 4
1 3 4 2 4
*/
详细
Test #1:
score: 100
Accepted
time: 80ms
memory: 67716kb
input:
4 4 2 5 5 2 4 2 1 3 3 2 1 4 3 5 4 3 1 1 1 6 6 6 3 5 4 3 2 3 1 1 2 3 5 2 1 3 2 1 5 1 1 3 4 1 3 4 2 4
output:
500000007 5 5 6 5 10 9 166666673 5 6 500000006 4 3 4 5
result:
ok 15 numbers
Test #2:
score: -100
Wrong Answer
time: 251ms
memory: 79884kb
input:
50000 5 508432375 168140163 892620793 578579275 251380640 3 4 4 1 3 346232959 736203130 186940774 655629320 607743104 1 863886789 1 364158084 18 864679185 463975750 558804051 604216585 694033700 499417132 375390750 337590759 467353355 111206671 983760005 984444619 322277587 138763925 205122047 97736...
output:
854665334 904343293 79561560 234208588 859123744 863886789 871186919 814243920 968784984 206455474 341020407 449261413 196759729 901433117 519383814 907574792 983760005 984444619 489899014 435736558 113628626 977360756 482247153 963066959 665922935 577926775 132646723 421298438 601054667 99438820...
result:
wrong answer 3rd numbers differ - expected: '590444253', found: '79561560'