제출 #1179094

#제출 시각아이디문제언어결과실행 시간메모리
1179094sleepntsheepTreasure Hunt (CEOI11_tre)C++20
컴파일 에러
0 ms0 KiB
#include<map> #include<algorithm> #include<cstdio> #include<cassert> #include<vector> #include<utility> #define printf(...) 42 #define puts(...) 42 struct LCT{ struct node{ int pa,c[2],rev; long long val,sum; node(){ pa=c[0]=c[1]=rev=0;val=sum=0; } }; std::vector<node>t; void sz(int n){ t.assign(n,node());} int nrt(int v){return t[t[v].pa].c[0]==v||t[t[v].pa].c[1]==v;} void tagrev(int v){ if(!v)return; t[v].rev^=1; std::swap(t[v].c[0],t[v].c[1]); } void pushdown(int v){ if(t[v].rev){ tagrev(t[v].c[0]);tagrev(t[v].c[1]); t[v].rev=0; } } void pushup(int v){ pushdown(t[v].c[0]);pushdown(t[v].c[1]);t[v].sum=t[v].val+t[t[v].c[0]].sum+t[t[v].c[1]].sum; } void rot(int v){ int p=t[v].pa,g=t[p].pa,d=t[p].c[1]==v; if(nrt(p))t[g].c[t[g].c[1]==p]=v; pushdown(v); t[p].c[d]=t[v].c[!d]; if(t[v].c[!d])t[t[v].c[!d]].pa=p; t[v].c[!d]=p; t[t[p].pa=v].pa=g; pushup(p);pushup(v); } void upd(int v){if(nrt(v))upd(t[v].pa);pushdown(v);} void splay(int v){ upd(v); for(int p;nrt(v);rot(v)) if(nrt(p=t[v].pa))rot((t[t[p].pa].c[1]==p)==(t[p].c[1]==v)?p:v); pushup(v); } void access(int v){ for(int w=0;v;v=t[w=v].pa)splay(v),t[v].c[1]=w,pushup(v); } void evert(int v){ access(v);splay(v);tagrev(v);} void split(int v,int w){evert(v);access(w);splay(w);} void link(int v,int w){ evert(v);access(w);splay(w);t[v].pa=w;} void cut(int v){ access(v);splay(v); t[t[v].c[0]].pa=0; t[v].c[0]=0;pushup(v);} }lc; std::vector<std::pair<int,int>>nei; int ii,jj,iii,skibidize[2222222]; std::map<int,int>sh,rsh,weigh[1000000]; void init() { ii=iii=1; lc.sz(2000000); jj=1000000; sh[1]=1; } void link_weight(int v,int w,int dist){ int x; x=weigh[v][w]=weigh[w][v]=++jj; lc.t[x].val=dist;lc.pushup(x); lc.link(x,v); lc.link(x,w); skibidize[x]=std::max(rsh[v],rsh[w])-dist+1; } void ensure_point(int i){ if(sh.count(i))return; auto it=std::lower_bound(nei.begin(),nei.end(),std::make_pair(i+1,-1)); assert(it!=nei.begin()); int ll=prev(it)->second,rr=it->second; rsh[sh[i]=++ii]=i; int x=weigh[sh[ll]][sh[rr]]; printf(" Killing %d between %d %d\n",x,sh[ll],sh[rr]); lc.evert(x); lc.cut(sh[ll]); lc.cut(sh[rr]); link_weight(sh[ll],ii,i-prev(it)->first+1); link_weight(sh[rr],ii,it->first-i); } void path(int a, int s) { ensure_point(a); nei.emplace_back(iii+1,a); iii+=s; rsh[sh[iii]=++ii]=iii; int b=iii; nei.emplace_back(iii,b); link_weight(sh[a],sh[b],s); } int take=0; int findright(int v,int k){ lc.pushdown(v); lc.pushup(v); int rightsum=lc.t[lc.t[v].c[1]].sum,cursum=rightsum+take+lc.t[v].val; printf(" -- %d %d %d -- %d %d %d\n",v,lc.t[v].c[0],lc.t[v].c[1],take,rightsum,lc.t[v].val); if(take+rightsum>=k){ return findright(lc.t[v].c[1],k); }else if(cursum>=k){ printf(" Got at %d = %d\n",v,cursum); take=cursum; return v; }else{ take=cursum; return findright(lc.t[v].c[0],k); } } int dig(int a, int b) { ensure_point(a); ensure_point(b); a=sh[a],b=sh[b]; lc.split(a,b); printf(" Try %d to %d\n",a,b); int ans; int lef=(lc.t[b].sum+1)/2; take=0; printf(" Want %d\n",lef); int v=findright(b,lef); printf(" Take=%d\n",take); lef=lc.t[b].sum/2-(lc.t[b].sum-take); printf(" Lef=%d\n",lef); if(lc.t[v].val==0){ //printf("%d\n",rsh[v]); puts("A"); ans=rsh[v]; }else if(lc.t[v].val==1){ //printf("%d\n",skibidize[v]); puts("B"); ans=skibidize[v]; }else{ puts("C"); ans=skibidize[v]-1+lef; // printf("%d\n",v); } lc.access(v); return ans; } #undef puts #undef printf

컴파일 시 표준 에러 (stderr) 메시지

/usr/bin/ld: /usr/lib/gcc/x86_64-linux-gnu/11/../../../x86_64-linux-gnu/crt1.o: in function `_start':
(.text+0x1b): undefined reference to `main'
collect2: error: ld returned 1 exit status