为什么使用vector会超时,而结构体数组不会?
查看原帖
为什么使用vector会超时,而结构体数组不会?
451352
Dongshi楼主2021/8/16 07:41

如题,第一段是使用vector的TLE代码,第二段是使用结构体数组的AC代码,按理说vector虽然慢一点但也不至于慢这么多吧,请问这是为什么?

#include<bits/extc++.h>
using namespace std;
#define endl '\n'
typedef int INT;
//#define int long long
inline int read(){
    int x=0,y=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')y=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return x*y;
}
inline void write_base(int x){
    if(x>9)write_base(x/10);
    putchar('0'+x%10);
}
inline void write(int x){
    if(x<0)putchar('-'),x*=-1;
    write_base(x);
//    putchar(' ');
    putchar('\n');
}
//using namespace __gnu_pbds;
/********************************************************/
const int N=1e3+1;
double x[N],y[N];
int fa[N];
inline int find(int i){
    int n=i;
    while(i!=fa[i])
        i=fa[i];
    return fa[n]=i;
}
struct Node{
    int a,b;double w;
    bool operator<(Node node){
        if(w==node.w)
            if(a==node.a)
                return b<node.b;
            else
                return a<node.a;
        else
            return w<node.w;
    }
};
inline double dis(int a,int b){
    return sqrt(pow(x[a]-x[b],2)+pow(y[a]-y[b],2));
}
vector<Node>v;
INT main(){//ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n=read(),m=read();
    for(register int i=1;i<=n;++i)
        x[i]=read(),y[i]=read(),fa[i]=i;
    for(register int i=1;i<=n;++i)
        for(register int j=i+1;j<=n;++j)
            v.push_back(Node{i,j,dis(i,j)}),
    sort(v.begin(),v.end());
    while(m--)
        fa[find(read())]=find(read());
    double ans=0;
    for(auto&i:v)
        if(find(i.a)!=find(i.b))
            fa[find(i.a)]=find(i.b),
            ans+=i.w;
    printf("%.2lf",ans);
}
#include<bits/extc++.h>
using namespace std;
#define endl '\n'
typedef int INT;
//#define int long long
inline int read(){
    int x=0,y=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')y=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return x*y;
}
inline void write_base(int x){
    if(x>9)write_base(x/10);
    putchar('0'+x%10);
}
inline void write(int x){
    if(x<0)putchar('-'),x*=-1;
    write_base(x);
//    putchar(' ');
    putchar('\n');
}
//using namespace __gnu_pbds;
/********************************************************/
const int N=1e3+1;
double x[N],y[N];
int fa[N];
inline int find(int i){
    int n=i;
    while(i!=fa[i])
        i=fa[i];
    return fa[n]=i;
}
struct Node{
    int a,b;double w;
    bool operator<(Node node){
        if(w==node.w)
            if(a==node.a)
                return b<node.b;
            else
                return a<node.a;
        else
            return w<node.w;
    }
}node[1000000];int t=0;
inline double dis(int a,int b){
    return sqrt(pow(x[a]-x[b],2)+pow(y[a]-y[b],2));
}
INT main(){//ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n=read(),m=read();
    for(register int i=1;i<=n;++i)
        x[i]=read(),y[i]=read(),fa[i]=i;
    for(register int i=1;i<=n;++i)
        for(register int j=i+1;j<=n;++j)
            node[t].a=i,node[t].b=j,node[t++].w=dis(i,j);
    sort(node,node+t);
    while(m--)
        fa[find(read())]=find(read());
    double ans=0;
    for(auto&i:node)
        if(find(i.a)!=find(i.b))
            fa[find(i.a)]=find(i.b),
            ans+=i.w;
    printf("%.2lf",ans);
}
2021/8/16 07:41
加载中...