QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#386210#7455. stcmOccDreamerTL 0ms0kbC++143.7kb2024-04-11 14:04:412024-04-11 14:04:41

Judging History

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

  • [2024-04-11 14:04:41]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2024-04-11 14:04:41]
  • 提交

answer

//code by Emissary
#include<bits/stdc++.h>

#define vc vector
#define db double
#define fi first
#define se second
#define ll long long
#define mk make_pair
#define pb push_back
#define RI register int
#define PI pair<int,int>
#define ull unsigned long long
#define err cerr << "   -_-   " << endl
#define debug cerr << " ------------------- " << endl

#define input(x) freopen(#x".in","r",stdin)
#define output(x) freopen(#x".out","w",stdout)

#define NO puts("No")
#define YES puts("Yes")

//#define OccDreamer
//#define int long long

using namespace std;

namespace IO{
	inline int read(){
		int X=0, W=0; char ch=getchar();
		while(!isdigit(ch)) W|=ch=='-', ch=getchar();
		while(isdigit(ch)) X=(X<<1)+(X<<3)+(ch^48), ch=getchar();
		return W?-X:X;
	}
	inline void write(int x){
		if(x<0) x=-x, putchar('-');
		if(x>9) write(x/10);
		putchar(x%10+'0');
	}
	inline void sprint(int x){write(x), putchar(32);}
	inline void eprint(int x){write(x), putchar(10);}
}using namespace IO;

const int MAXN = 5e6+5;

int tot, All;
int node, lc[MAXN], rc[MAXN];
int son[MAXN], siz[MAXN], fa[MAXN];
int n, id[MAXN], toid[MAXN], topf[MAXN];
int head[MAXN], ne[MAXN<<1], to[MAXN<<1], cnt;

struct huff{
	int x, sz;
	inline bool friend operator < (const huff &x, const huff &y){return x.sz>y.sz;}
};

inline void Del(){putchar('-');}
inline void Add(int x){putchar('+'); write(x); All++;}
inline void report(int x){putchar('='); write(x);}

inline void add(int x, int y){++cnt;to[cnt]=y;ne[cnt]=head[x];head[x]=cnt;}

inline void dfs1(int x, int f){
	siz[x]=1; fa[x]=f; son[x]=0;
	for(int i=head[x];i;i=ne[i]){
		if(to[i]==f) continue;
		dfs1(to[i],x); siz[x]+=siz[to[i]];
		if(siz[to[i]]>siz[son[x]]) son[x]=to[i];	
	}
	return ;
}

inline void dfs2(int x, int tp){
	topf[x]=tp; id[x]=++tot; toid[tot]=x;
	if(son[x]) dfs2(son[x],tp);
	for(int i=head[x];i;i=ne[i]){
		if(to[i]==fa[x] || to[i]==son[x]) continue;	
		dfs2(to[i],to[i]);
	}
}	

inline void addtree(int x){
	for(int i=id[x];i<=id[x]+siz[x]-1;++i) Add(toid[i]);
	return ;	
}

inline void deltree(int x){
	for(int i=id[x];i<=id[x]+siz[x]-1;++i) Del();
	return ;
}

inline void Run(int now);

inline void construct(int x){
	report(x);
	for(int i=head[x];i;i=ne[i]){
		if(to[i]==son[x]) continue;
		addtree(to[i]);	
	}
	Add(x);
	if(son[x]) construct(son[x]);
	Del();
	for(int i=head[x];i;i=ne[i]){
		if(to[i]==son[x]) continue;
		deltree(to[i]);	
	}
	if(topf[x]==x){
		priority_queue<huff> Q;
		int now=x;
		while(now){
			Add(now);
			for(int i=head[now];i;i=ne[i]){
				if(to[i]==son[now]) continue;
				Q.push(huff{to[i],siz[to[i]]});
			}
			now=son[now];
		}
		if(Q.size()){
			if(Q.size()==1) construct(Q.top().x);
			else{
				while(Q.size()>=2){
					huff A, B;
					A=Q.top(); Q.pop();
					B=Q.top(); Q.pop();	
					++node; lc[node]=A.x; rc[node]=B.x; Q.push(huff{node,A.sz+B.sz});
				}
				Run(Q.top().x);
			}
		}
		now=x;
		while(now){
			Del();
			now=son[now];	
		}
	}
}

inline void adddfs(int x){
	if(x<=n) addtree(x);
	if(lc[x]) adddfs(lc[x]);
	if(rc[x]) adddfs(rc[x]);
	return ;	
}

inline void deldfs(int x){
	if(x<=n) deltree(x);
	if(lc[x]) deldfs(lc[x]);
	if(rc[x]) deldfs(rc[x]);
	return ;	
}

inline void Run(int x){
	if(x<=n) construct(x);
	else{
		adddfs(rc[x]);
		Run(lc[x]); deldfs(rc[x]); adddfs(lc[x]);
		Run(rc[x]); deldfs(lc[x]);
	}
	return ;
}
	
inline void solve(){
	int x; tot=0; All=0; node=n;
	for(int i=1;i<=n;++i) head[i]=0, lc[i]=rc[i]=0; cnt=0;
	for(int i=2;i<=n;++i) x=rand()%(i-1)+1, add(x,i);
	dfs1(1,0); dfs2(1,1); construct(1);
	putchar('!'); putchar(10);
}	

signed main(){
	while(scanf("%d",&n)!=EOF) solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Time Limit Exceeded

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+59+211+370+931+35+39+114+195+498+486+989+519+361+156+929+676+790+849+734+109+128+245+712+443+617+769+674+447+171+383+545+985+863+679+390+267+303+777+971+537+258+175+588+44+89+972+265+19+27+28+120+170+215+466+467+821+982+692+642+607+955+263+257+724+871+892+805+253+414+189+662+380+867+229+708+182+1...

result: