59 条题解
-
2
938936 LV 8 @ 2018-02-15 14:38:11
#1 Accepted 6ms 772.0 KiB
#2 Accepted 5ms 2.875 MiB
#3 Accepted 9ms 892.0 KiB
#4 Accepted 14ms 996.0 KiB
#5 Accepted 46ms 1.273 MiB
#6 Accepted 69ms 1.945 MiB
#7 Accepted 145ms 4.535 MiB
#8 Accepted 135ms 6.383 MiB
#9 Accepted 340ms 6.5 MiB
#10 Accepted 327ms 6.453 MiB很水的做法:
离线处理最终状态,并查集特判不同列情况#include<iostream> #include<cmath> using namespace std; int n=30000,q,fa[30001],f[30001],ta[30001],val[30001]; struct cz{ char c; int a,b; }op[500001]; int find(int); int main(){ ios::sync_with_stdio(false); cin>>q; int i,p; for(i=1;i<=n;i++){ fa[i]=f[i]=ta[i]=i; } for(i=1;i<=q;i++){ cin>>op[i].c; cin>>op[i].a>>op[i].b; if(op[i].c=='M'){ int x=find(op[i].a),y=find(op[i].b); fa[x]=y; f[x]=ta[y]; ta[y]=ta[x]; ta[x]=0; } } p=0; for(i=1;i<=n;i++){ fa[i]=i; if(ta[i]==0) continue; int v=ta[i]; val[v]=++p; while(f[v]!=v){ v=f[v]; val[v]=++p; } } for(i=1;i<=q;i++){ int a=find(op[i].a),b=find(op[i].b); if(op[i].c=='M'){ fa[a]=b; }else{ if(a!=b){ cout<<-1<<endl; continue; } cout<<abs(val[op[i].a]-val[op[i].b])-1<<endl; } } return 0; } int find(int v){ return fa[v]==v?v:fa[v]=find(fa[v]); } -
2
const
maxn=30000;
type
node=record
p,d,l :integer;
end;
var
uf :array[1..maxn]of node;
n,m :longint;
a,b,i :longint;
c :char;
procedure init;
var
i :integer;
begin
n:=30000;
readln(m);
for i:=1 to n do
with uf[i] do begin p:=i; l:=1 end;
end;function find(x:integer):integer;
var
i,j,p,q :integer;
begin
i:=x;
while uf[i].p<>i do i:=uf[i].p;
p:=i;
i:=x;
while i<>p do
begin
q:=uf[i].p;
uf[i].p:=p;
j:=q;
repeat
inc(uf[i].d,uf[j].d);
j:=uf[j].p
until uf[j].p=j;
i:=q;
end;
find:=p;
end;procedure union(a,b:integer);
var
t :integer;
begin
a:=find(a); b:=find(b);
uf[a].p:=b;
uf[a].d:=uf[b].l;
inc(uf[b].l,uf[a].l)
end;
begin
init;
for i:=1 to m do
begin
readln(c,a,b);
if c='M' then union(a,b);
if c='C' then
if (find(a)=find(b)) then
writeln(abs(uf[a].d-uf[b].d)-1)
else writeln(-1)
end;
end. -
1
很基础的一道并查集……
#include<bits/stdc++.h> using namespace std; int p,f[30010],dis[30010],sum[30010],x,y,fx,fy; char c; int find(int x) { if(f[x]==x) return f[x]; int temp=f[x]; f[x]=find(f[x]); dis[x]+=dis[temp]; return f[x]; } void Union(int x,int y) { fx=find(x),fy=find(y); f[fx]=fy; dis[fx]=sum[fy]; sum[fy]+=sum[fx]; } int main() { for(int i=1;i<=30000;i++) f[i]=i,dis[i]=0,sum[i]=1; scanf("%d",&p); for(int i=1;i<=p;i++) { scanf(" %c",&c); if(c=='M') { scanf("%d%d",&x,&y); Union(x,y); } else { scanf("%d%d",&x,&y); fx=find(x),fy=find(y); if(fx!=fy) puts("-1"); else printf("%d\n",abs(dis[x]-dis[y])-1); } } return 0; } -
1
从并查集本身树结构思考
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<string> #include<cmath> #define MAXN 30005 using namespace std; int ufs[MAXN], dis[MAXN] = {0}, ecnt[MAXN]; void init(int n){ for(int i=0; i<=n; i++){ ufs[i] = i; ecnt[i] = 1; } return; } int find(int a){ int rt = a, ta = a, tta, tcnt; int cnt = 0; while(ufs[rt] != rt){ cnt += dis[rt]; rt = ufs[rt]; } while(ufs[ta] != ta){ tta = ta; tcnt = dis[ta]; dis[ta] = cnt; cnt -= tcnt; ta = ufs[ta]; ufs[tta] = rt; } return rt; } void unite(int a, int b){ int rta, rtb; int tcnta, tcntb; rta = find(a); rtb = find(b); if(rta == rtb){ return; } ufs[rta] = rtb; tcnta = ecnt[rta]; tcntb = ecnt[rtb]; ecnt[rta] = 0; ecnt[rtb] = tcnta + tcntb; dis[rta] = tcntb; return; } int sameufs(int a, int b){ if(a == b){ return 0; } if(find(a) != find(b)){ return -1; }else{ return abs(dis[a] - dis[b]) - 1; } } int main(){ int n; string s; cin >> n; int x, y; init(30000); for(int i=0; i<n; i++){ cin >> s >> x >> y; if(s == "M"){ unite(x, y); }else if(s == "C"){ cout << sameufs(x, y) << endl; } } return 0; } -
0
经典并查集+预先处理
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=100000+10;
typedef long long ll;
//priority_queue<int> a;
//priority_queue<int,vector<int>,greater<int> > a1;
int n,m,k;
//continue;
int a,b;
int f[N],w[N];
char w1[2];
int rk[N];
int getfather(int x)
{
if(f[x]==x)
return x;
int tmp=f[x];
f[x]=getfather(f[x]);
rk[x]=rk[tmp]+rk[x]-1;
return f[x];
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=N;i++)
{
f[i]=i;
w[i]=1;
rk[i]=1;
}
for(int i=1;i<=n;i++)
{
scanf("%s %d %d",w1,&a,&b);
int u=getfather(a);
int v=getfather(b);
if(w1[0]=='M')
{
if(u!=v)
{
f[v]=u;
rk[v]+=w[u];
w[u]+=w[v];
}
}
else
{
if(u!=v)
printf("-1\n");
else
printf("%d\n",abs(rk[a]-rk[b])-1);
}
}
return 0;
}
//2434 -
0
kevinshuai LV 8 @ 2017-01-16 19:32:42
wc这道题疯狂拉AC率。
我写了两份代码，第一份T了最后两个点，然后在第二份中修改，结果每次提交成了第一份。
TLE的原因是用了cin。被卡常了。真是zz。 -
0
-
0
zhhf666666 LV 4 @ 2016-10-12 13:04:45
#include<iostream>
using namespace std;
int pre[30001];
int find(int x)
{
int r=x;
while(pre[r]!=r)
r=pre[r];int i=x,j;
while(i!=j)
{
j=pre[r];
pre[i]=r;
i=j;
}
return r;
}
void mix(int x,int y)
{
int fx=find(x),fy=find(y);
if(fx!=fy)
pre[fx]=fy;
}
int main()
{
int i,t,a,b,j;
char g;
for(i=1;i<=30000;i++)
pre[i]=i;
cin>>t;
for(i=1;i<=t;i++)
{
cin>>g>>a>>b;
if(g=='M')
{
mix(a,b);
}
if(g=='C')
{
if(find(a)==find(b))
cout<<"1"<<endl;
else
cout<<"-1"<<endl;
}
}}
-
0
caesar_199 LV 9 @ 2016-08-24 08:36:23
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int INF = 1000000000; const int maxn = 30000 + 10; int p[maxn], d[maxn], cnt[maxn]; int find (int x) { if (x == p[x]) return x; int root = find(p[x]); d[x] += d[p[x]]; return p[x] = root; } void comb (int x, int y) { int a = find(x), b = find(y); p[b] = a; d[b] = cnt[a]; cnt[a] += cnt[b]; } int query (int x, int y) { int a = find(x), b = find(y); if (a != b) return -1; return abs(d[x]-d[y])-1; } int main () { freopen("in.txt", "r", stdin); for (int i = 0; i < maxn; i++) { p[i] = i; cnt[i] = 1;} int T; scanf("%d\n", &T); while (T--) { char code; int i, j; scanf("%c %d %d\n", &code, &i, &j); if (code == 'M') comb(j, i); else printf("%d\n", query(i, j)); } return 0; } -
0
#include<cstdio>
#include<cmath>
const int Max=30001;
int t,father[Max],x,y,r[Max],root[Max];
char ch;
int find(int k){
if(k==father[k]) return k;
int temp=find(father[k]);
r[k]=r[father[k]]+r[k];
father[k]=temp;
return temp;
}
int main(){
scanf("%d",&t);
for(int i=1;i<Max;i++){
father[i]=i; r[i]=0,root[i]=1; //r表示到根节点的距离
} //root 表示该树节点个数
while(t--){
getchar();
scanf("%c%d%d",&ch,&x,&y);
int tempx=find(x),tempy=find(y);
if(ch=='M'){
father[tempx]=tempy; //X 接到 y
r[tempx]=root[tempy]; //更新距离
root[tempy]+=root[tempx]; //更新树节点个数
}
else if(tempx!=tempy) printf("-1\n");
else printf("%d\n",(int)fabs(r[x]-r[y])-1);
}
return 0;
} -
0
#include <iostream> #include <cstdio> #include <cmath> #include <algorithm> using namespace std; int f[30001],s[30001],sum[30001]; char ch_buffer; int signum; inline void read(int&x){ x=0;char c; for(c=getchar();c<'0'||c>'9';c=getchar()); for(;c>='0'&&c<='9';c=getchar())x=(x<<3)+(x<<1)+c-'0'; } int find(int v){ if(f[v]!=v){ int p=find(f[v]); s[v]+=s[f[v]]; f[v]=p; } return f[v]; } int main(){ ios::sync_with_stdio(false); cin.tie(NULL); //freopen("in.in","r",stdin); int f1,f2,num,a,b; char ch; read(num); for(int i=1;i<=30000;i++){sum[i]=1;f[i]=i;} for(int i=1;i<=num;i++){ ch=getchar(); read(a),read(b); f1=find(a),f2=find(b); //cout<<a<<b; if(ch=='M'){ f[f1]=f2; s[f1]=sum[f2]; sum[f2]+=sum[f1]; } else{ if(f1==f2)cout<<abs(s[a]-s[b])-1<<"\n"; else cout<<"-1\n"; } } return 0; } -
0
HeRaNO (heran1999) LV 10 @ 2016-02-25 19:47:31
//直接并查集~~ #include <iostream> #include <cstdio> #include <cmath> #define MAXN 31000 using namespace std; struct node { int fa; int d;//i飞船前面有多少飞船 b int l;//当i是并查集根时，i后面有多少飞船 c }; char flag; node f[MAXN]; int i,t,x,y; int getfather (int x) { int t; if (x==f[x].fa) return x; t=f[x].fa; f[x].fa=getfather(f[x].fa); f[x].d+=f[t].d; return f[x].fa; } void merg (int x,int y) { int tx=getfather(x); int ty=getfather(y); if (tx!=ty) { f[tx].fa=ty; f[tx].d=f[ty].l+1; f[ty].l=f[ty].l+f[tx].l+1; } } int query (int x,int y) { if (getfather(x)==getfather(y)) return (abs(f[x].d-f[y].d)-1); else return -1; } int main() { for (i=1;i<=MAXN;i++) { f[i].fa=i; f[i].d=0; f[i].l=0; } scanf("%d\n",&t); for (i=1;i<=t;i++) { scanf("%c %d %d\n",&flag,&x,&y); if (flag=='M') merg(x,y); else printf("%d\n",query(x,y)); } return 0; } -
0
P1443银河英雄传说
Accepted记录信息
评测状态 Accepted
题目 P1443 银河英雄传说
递交时间 2015-11-15 22:55:41
代码语言 C++
评测机 VijosEx
消耗时间 5238 ms
消耗内存 628 KiB
评测时间 2015-11-15 22:55:49评测结果
编译成功
测试数据 #0: Accepted, time = 0 ms, mem = 628 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 628 KiB, score = 10
测试数据 #2: Accepted, time = 15 ms, mem = 628 KiB, score = 10
测试数据 #3: Accepted, time = 62 ms, mem = 624 KiB, score = 10
测试数据 #4: Accepted, time = 202 ms, mem = 628 KiB, score = 10
测试数据 #5: Accepted, time = 483 ms, mem = 624 KiB, score = 10
测试数据 #6: Accepted, time = 499 ms, mem = 628 KiB, score = 10
测试数据 #7: Accepted, time = 639 ms, mem = 624 KiB, score = 10
测试数据 #8: Accepted, time = 1856 ms, mem = 628 KiB, score = 10
测试数据 #9: Accepted, time = 1482 ms, mem = 624 KiB, score = 10
Accepted, time = 5238 ms, mem = 628 KiB, score = 100
why so slow
代码
#include <iostream>
#include <stdio.h>
#include <string.h>using namespace std;
int pre[30000 + 2] , size[30000 + 2] , tail[30000 + 2];
int n , a , b , x , y;
char s[10];int find( int x )
{
if( pre[x] == x ) return x;
int pos = pre[x];
pre[x] = find( pre[x] );
size[x] += size[pos];
return pre[x];
}inline void merge( int a , int b )
{
pre[ find( a ) ] = find( b );
}inline int Abs( int x )
{
return x > 0 ? x : -x;
}int main()
{
scanf( "%d" , &n );
for( register int i = 1 ; i <= 30000 ; i++ )
pre[i] = i , tail[i] = 1;
while( n-- )
{
scanf( "%s %d %d" , s , &a , &b );
if( s[0] == 'C' )
{
if( find( a ) != find( b ) ) puts( "-1" );
else printf( "%d\n" , Abs( size[a] - size[b] ) - 1 );
}
else
{
x = find( a ) , y = find( b );
merge( a , b );
size[ x ] += tail[ y ];
tail[ y ] += tail[ x ];
}
}
return 0;
} -
0
#include<cmath>
#include<cstdio>
#include<iostream>
using namespace std;
char t;
int m,q,a,b,f[30001],o[30001]={0},c[30001];
void r(int&d)
{
char t=getchar();
while(t<'0'||t>'9')
t=getchar();
for(d=0;t>='0'&&t<='9';t=getchar())
d=(d<<3)+(d<<1)+t-'0';
}
int find(int n)
{
int d;
if(n==f[n])
return n;
else
{
d=find(f[n]);
o[n]+=o[f[n]];
f[n]=d;
return f[n];
}
}
bool e(int x,int y)
{
int p,q;
p=find(x);
q=find(y);
if(p==q)
return 1;
else
{
f[q]=p;
o[q]+=c[p];
c[p]+=c[q];
return 0;
}
}
main()
{
char k[100];
int d,i,j;
cin>>q;
for(i=1;i<30001;i++)
{
f[i]=i;
c[i]=1;
}
for(i=0;i!=q;i++)
{
t=getchar();
while(t!='M'&&t!='C')
t=getchar();
r(a);
r(b);
if(t=='M')
e(a,b);
else
if(find(a)==find(b))
{
d=abs(o[b]-o[a])-1;
j=1;
if(d<0)
{
cout<<'-';
d=-d;
}
if(!d)
cout<<0;
for(;d;d/=10,j++)
k[j]=d%10+'0';
for(j--;j;j--)
cout<<k[j];
cout<<endl;
}
else
cout<<-1<<endl;
}
} -
0
#include<cstdio>
int n=30000,m,q;
int ai,bi;
int fath[30001];
int count[30001];
int before[30001];
char t;
inline void _out(int x,int j=1)
{
char t[100];
if(x<0)
{
putchar('-');
x=-x;
}
if(x==0) printf("0");
for(;x;x/=10,j++) t[j]=x%10+'0';
for(j--;j;j--) putchar(t[j]);
putchar('\n');
}inline void _read(int& data)
{
char t=getchar();
while(t<'0'||t>'9') t=getchar();
for(data=0;t>='0'&&t<='9';t=getchar()) data=(((data)<<3)+((data)<<1))+t-'0';
}int getfather(int num)
{
int dad;
if(num==fath[num]) return num;
else
{
dad=getfather(fath[num]);
before[num]=before[num]+before[fath[num]];
fath[num]=dad;
return fath[num];
}
}
bool merge(int x,int y)
{
int fx,fy ;
fx=getfather(x);
fy=getfather(y);
if (fx==fy) return true;
else
{
fath[fy]=fx;
before[fy]=before[fy]+count[fx];
count[fx]=count[fx]+count[fy];
return false;
}
}inline void _init()
{
scanf("%d",&q);
for(int i=1;i<=n;++i)
{fath[i]=i;count[i]=1;before[i]=0;}
}
inline int abs(int a)
{return a<0?(-a):a;}
int main()
{
_init();
for(int i=0;i!=q;++i)
{
t=getchar();
while(t!='M'&&t!='C') t=getchar();
if(t=='M'){_read(ai);_read(bi); merge(ai,bi);}
else
{ _read(ai);_read(bi);
if(getfather(ai)==getfather(bi))_out((abs(before[bi]-before[ai]))-1);
else {putchar('-');putchar('1');putchar('\n');}
}
}
return 0;
} -
0
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
long f[30100],s[30100],sum[30100];
int getfather(int v){
if (f[v]!=v){
int p=getfather(f[v]);
s[v]+=s[f[v]];
f[v]=p;
}return f[v];
}
int main(){
int f1,f2,num,a,b; char ch;
scanf("%d\n",&num);
for(int i=1;i<=30000;i++) {s[i]=0; sum[i]=1; f[i]=i;}
for(int i=1;i<=num;i++){
scanf("%c %d %d\n",&ch,&a,&b);
f1=getfather(a),f2=getfather(b);
if(ch=='M'){
f[f1]=f2;
s[f1]=sum[f2];
sum[f2]+=sum[f1];
}else if(ch=='C'){
if(f1==f2) printf("%d\n",abs(s[a]-s[b])-1);
else printf("-1\n");
}
}
return 0;
} -
0
编译成功
foo.cpp: In function 'int main()':
foo.cpp:57:26: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[1]' [-Wformat]
测试数据 #0: Accepted, time = 7 ms, mem = 1004 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 1004 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 1004 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 1000 KiB, score = 10
测试数据 #4: Accepted, time = 62 ms, mem = 1004 KiB, score = 10
测试数据 #5: Accepted, time = 93 ms, mem = 1004 KiB, score = 10
测试数据 #6: Accepted, time = 140 ms, mem = 1000 KiB, score = 10
测试数据 #7: Accepted, time = 203 ms, mem = 1004 KiB, score = 10
测试数据 #8: Accepted, time = 343 ms, mem = 1004 KiB, score = 10
测试数据 #9: Accepted, time = 468 ms, mem = 1000 KiB, score = 10
Accepted, time = 1331 ms, mem = 1004 KiB, score = 100
#include <cstdio>
#include <cstring>using namespace std;
#define MAXN 30001
int father[MAXN];
int tail[MAXN],head[MAXN];
int suff[MAXN];int t;
char c[1];int ABS(int x){
if (x<0){
return -x;
}
return x;
}int INSERT(int x,int y){
father[x]=y;
suff[x]++;
return 0;
}int find(int x){
int i=x;
int k=0;
while (father[i]){
k+=suff[i];
k--;
i=father[i];
}
k++;
int j=x;
while (father[j]){
int h=father[j],z=suff[j];
suff[j]=k;
k-=(z-1);
father[j]=i;
j=h;
}
return i;
}int main(){
memset(father,0,sizeof(father));
for (int i=0;i++<MAXN;){
tail[i]=head[i]=i;
suff[i]=1;
}
scanf("%d",&t);
while (t--){
int x,y;
scanf("%s%d%d",&c,&x,&y);
if (c[0]=='M'){
int k=tail[find(x)];
INSERT(find(x),tail[find(y)]);
tail[find(y)]=k;
} else {
if (find(x)!=find(y)){
printf("-1\n");
} else printf("%d\n",ABS(suff[x]-suff[y])-1);
}
}
return 0;
} -
0
sliverzero LV 8 @ 2010-03-18 13:48:00
我无语...自己机上测这条题（使用VJ数据）近乎秒，这里超时+格式错误+答案错误....T-T
938936
LV 8
@ 2018-02-15 14:38:11
