QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#391225#7455. stcmLynkcatWA 110ms8384kbC++171.8kb2024-04-16 14:51:542024-04-16 14:51:54

Judging History

你现在查看的是最新测评结果

  • [2024-04-16 14:51:54]
  • 评测
  • 测评结果:WA
  • 用时:110ms
  • 内存:8384kb
  • [2024-04-16 14:51:54]
  • 提交

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