F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
大视野在线测评-欢迎您
[ New Thread ]
MainBoard >> 新人求助,永无乡那题,本机AC,提交CE。。。
xiangrui @ 2018-12-28 09:50:44
[ Quote ] [ Edit ] [ Delete ] 1#
代码:
#include<bits/stdc++.h>
#define N 5000001
using namespace std;
int n,m,q,rt[N],fa[N],pos[N]={-1};
inline int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
struct sgt{
int sz[N],ls[N],rs[N],tot;
inline void update(int x){sz[x]=sz[ls[x]]+sz[rs[x]];}
inline void add(int &q,int x,int l,int r){
if(!q)q=++tot;
if(l==r){sz[q]=1;return ;}
int mid=(l+r)>>1;
if(mid>=x)add(ls[q],x,l,mid);
else add(rs[q],x,mid+1,r);
update(q);
}
inline int merge(int x,int y){
if(!x||!y)return x+y;
ls[x]=merge(ls[x],ls[y]);
rs[x]=merge(rs[x],rs[y]);
update(x);
return x;
}
inline int query(int q,int l,int r,int k){
if(sz[q]<k)return 0;
if(l==r)return l;
int mid=(l+r)>>1;
if(sz[ls[q]]>=k)return query(ls[q],l,mid,k);
return query(rs[q],mid+1,r,k-sz[ls[q]]);
}
inline void newbridge(int x,int y){
int f1=find(x),f2=find(y);
if(f1!=f2)fa[f2]=f1,merge(rt[f1],rt[f2]);
}
}T;
inline int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
int main(){
n=read(),m=read();
for(int i=1;i<=n;i++){
int x=read();
fa[i]=i,pos[x]=i,T.add(rt[i],x,1,n);
}
for(int i=1;i<=m;i++){
int x=read(),y=read();
T.newbridge(x,y);
}
q=read();
for(int i=1;i<=q;i++){
char ch[1];scanf("%s",ch);
int l=read(),r=read();
if(ch[0]=='Q')printf("%d\n",pos[T.query(rt[find(l)],1,n,r)]);
else T.newbridge(l,r);
}
return 0;
}
CE警告:
Main.cc: In function 'int main()':
Main.cc:54: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result
g++: Internal error: File size limit exceeded (program as)
Please submit a full bug report.
See <file:///usr/share/doc/gcc-4.4/README.Bugs> for instructions.
yuqifeng @ 2018-12-28 09:53:22
[ Quote ] [ Edit ] [ Delete ] 2#
代码明显有问题,你本机是怎么A的。。
ezoixx130 @ 2018-12-28 10:12:18
[ Quote ] [ Edit ] [ Delete ] 3#
数组爆了吧
nn020701 @ 2018-12-28 11:33:24
[ Quote ] [ Edit ] [ Delete ] 4#
应该是你那个char数组ch的问题,长度为1……要知道char的很多操作是要等到出现0才结束。长度起码开大点。(而且长度为1为什么要开数组……)
nn020701 @ 2018-12-28 11:34:07
[ Quote ] [ Edit ] [ Delete ] 5#
我怀疑就是它就是觉得你开长度为1的数组太蠢了
Ycrpro @ 2019-01-06 22:46:33
[ Quote ] [ Edit ] [ Delete ] 6#
楼上们都是在干啥。。。
pos[N]={-1};这么写会编译出巨大的exe导致CE
<\del>感觉给好多人说过这东西了<\del>
[Top] [Previous Page] [Next Page]

HOME Back