QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #320175 | #8212. Football in Osijek | ucup-team052# | WA | 2ms | 7924kb | C++23 | 2.4kb | 2024-02-03 14:21:53 | 2024-02-03 14:21:54 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
//mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define mod 998244353
#define ll long long
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
inline int read()
{
char ch=getchar(); int nega=1; while(!isdigit(ch)) {if(ch=='-') nega=-1; ch=getchar();}
int ans=0; while(isdigit(ch)) {ans=ans*10+ch-48;ch=getchar();}
if(nega==-1) return -ans;
return ans;
}
void print(vector<int> x){for(int i=0;i<(int)x.size();i++) printf("%d%c",x[i]," \n"[i==(int)x.size()-1]);}
#define N 500005
int a[N],n;
int vis[N],vis2[N],rt[N],siz[N],cir[N];
int ok[N],pre[N];
vector<int> G[N];
struct Node{int c,s;};
Node b[N];
int mxd[N],dep[N];
int dfs(int u)
{
dep[u]=dep[a[u]]+1;
int mxd=dep[u];
for(int v:G[u]) mxd=max(mxd,dfs(v));
return mxd;
}
signed main()
{
cin>>n;
for(int i=1;i<=n;i++) a[i]=read(),G[a[i]].push_back(i);
for(int i=1;i<=n;i++)
{
if(vis[i]) continue;
// printf("%d\n",i);
int cur=i,r=0,cnt=0,cc=0;
while(vis[cur]<=1&&!vis2[cur])
{
vis[cur]++;
if(vis[cur]==2) cc++;
else cnt++;
if(vis[cur]==2&&!r) r=cur;
// printf("%d %d %d %d * %d\n",cur,cnt,r,cc,rt[cur]);
cur=a[cur];
}
if(!r) r=rt[cur];
cur=i;
while(vis2[cur]==0)
{
rt[cur]=r;
vis2[cur]=1;
cur=a[cur];
}
// printf("%d %d %d\n",cur,cnt,rt[cur]);
siz[rt[cur]]+=cnt;
if(cc) cir[rt[cur]]=cc;
}
// for(int i=1;i<=n;i++) printf("%d%c",vis[i]," \n"[i==n]);
// for(int i=1;i<=n;i++) printf("%d %d\n",siz[i],cir[i]);
for(int i=1;i<=n;i++)
{
if(vis[i]==2)
{
int d=0;
for(int v:G[i]) if(vis[v]==1) d=max(d,dfs(v));
mxd[rt[i]]=max(mxd[rt[i]],d);
}
}
for(int i=1;i<=n;i++) if(siz[i]) ok[cir[i]]++,ok[cir[i]+mxd[i]+1]--;
for(int i=1;i<=n;i++) ok[i]+=ok[i-1];
for(int i=1;i<=n;i++) if(!pre[i]) pre[i]=pre[i-1];
int m=0;
for(int i=1;i<=n;i++)
{
if(siz[i]) b[++m]=(Node){cir[i],cir[i]+mxd[i]};
}
sort(b+1,b+m+1,[&](Node x,Node y){return x.s<y.s;});
vector<int> w; w.push_back(b[m].s);
for(int i=m-1;i>=1;i--) w.push_back(w.back()+b[i].s);
while(w.back()<n) w.push_back(w.back()+1);
int pos=0;
for(int i=1;i<=n;i++)
{
if(ok[i]) ok[i]=0;
else
{
while(i>w[pos]) pos++;
ok[i]=max(pos,1);
}
}
for(int i=1;i<=n;i++) printf("%d%c",ok[i]," \n"[i==n]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 7800kb
input:
5 2 3 1 3 5
output:
0 1 0 0 1
result:
ok 5 number(s): "0 1 0 0 1"
Test #2:
score: 0
Accepted
time: 2ms
memory: 7904kb
input:
1 1
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 1ms
memory: 5880kb
input:
2 2 2
output:
0 0
result:
ok 2 number(s): "0 0"
Test #4:
score: 0
Accepted
time: 2ms
memory: 7836kb
input:
10 4 7 2 8 4 3 4 9 7 3
output:
1 1 1 0 0 0 0 1 2 3
result:
ok 10 numbers
Test #5:
score: 0
Accepted
time: 1ms
memory: 5788kb
input:
10 8 7 4 8 3 4 2 5 3 7
output:
1 0 0 0 0 1 1 1 2 3
result:
ok 10 numbers
Test #6:
score: -100
Wrong Answer
time: 2ms
memory: 7924kb
input:
10 7 1 4 1 6 1 1 10 5 7
output:
1 0 0 0 0 1 2 3 4 5
result:
wrong answer 7th numbers differ - expected: '1', found: '2'