QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#386210 | #7455. stcm | OccDreamer | TL | 0ms | 0kb | C++14 | 3.7kb | 2024-04-11 14:04:41 | 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...