QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#391225 | #7455. stcm | Lynkcat | WA | 110ms | 8384kb | C++17 | 1.8kb | 2024-04-16 14:51:54 | 2024-04-16 14:51:54 |
Judging History
answer
#include<bits/stdc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e18
#define mod 998244353
#define sz(x) (int)((x).size())
//#define int ll
//#define N
using namespace std;
const int N=100005;
int dfn[N],idfn[N],rdfn[N];
int DFN;
poly G[N];
vector<pa>all;
int n;
void add(int x)
{
cout<<"+"<<x;
}
void undo()
{
cout<<"-";
}
void dfs(int k,int fa)
{
dfn[k]=++DFN;
idfn[DFN]=k;
for (auto u:G[k])
{
if (u==fa) continue;
dfs(u,k);
}
rdfn[k]=DFN;
all.push_back(mp(dfn[k],rdfn[k]));
}
int lpos,rpos;
void work(int l,int r,vector<pa>all)
{
if (l>r) return;
int mid=l+(r-l)/2;
vector<pa>lf,rt;
for (auto [x,y]:all)
if (x<=mid&&y>=mid)
{
while (lpos<x)
{
add(idfn[lpos++]);
}
while (rpos>y)
{
add(idfn[rpos--]);
}
cout<<"="<<idfn[x];
} else
if (y<mid) lf.push_back(mp(x,y));
else if (x>mid) rt.push_back(mp(x,y));
if (l==r) return;
while (lpos>l)
{
undo();
lpos--;
}
while (rpos<r)
{
undo();
rpos++;
}
if (l<mid)
{
while (rpos>=mid)
{
add(idfn[rpos--]);
}
work(l,mid-1,lf);
while (rpos<r) undo(),rpos++;
}
if (r>mid)
{
while (lpos<=mid)
{
add(idfn[lpos++]);
}
work(mid+1,r,rt);
while (lpos>l) undo(),lpos--;
}
}
void BellaKira()
{
for (int i=1;i<n;i++)
{
int x;
cin>>x;
// cout<<x<<" "<<i+1<<endl;
G[x].push_back(i+1);
}
dfs(1,0);
lpos=1,rpos=n;
reverse(all.begin(),all.end());
work(1,n,all);
cout<<'\n';
for (int i=1;i<=n;i++) poly().swap(G[i]);
DFN=0;
vector<pa>().swap(all);
}
signed main()
{
IOS;
cin.tie(0);
int T=1;
while (cin>>n)
{
BellaKira();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 110ms
memory: 8384kb
input:
1000 1 1 2 1 1 2 2 7 2 7 3 11 10 6 4 8 10 13 16 2 19 7 6 18 6 2 16 27 21 14 6 14 14 29 12 13 3 27 28 27 2 34 26 27 44 14 30 25 7 50 47 1 36 24 4 32 10 20 53 52 61 23 43 39 2 15 47 9 14 54 48 53 36 14 14 66 76 55 17 67 21 22 18 25 67 75 7 48 21 6 35 11 31 41 63 28 6 98 51 3 29 52 102 77 27 58 39 64 9...
output:
=1+1+772+569+940+882+812+494+243+968+773+732+727+570+441+905+754+435+980+665+426+323+843+798+622+412+206+177+619+590+175+994+778+129+873+691+650+523+468+136+73+531+195+60+53+661+548+368+983+837+319+601+421+362+342+696+678+481+291+202+874+649+521+764+247+663+598+347+346+936+400+290+192+167+473+745+40...
result:
wrong answer -1 / -1 / -1