map 20pts求调
查看原帖
map 20pts求调
745852
tzhlljy楼主2024/8/26 16:29

用的map,时间复杂度O(n*m),为什么只有20分?

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 5e4+5;
int n,m,ans;

struct node{
    int a,b,c;

    bool operator < (const node &B) const {
        if(a == B.a){
            if(b == B.b)
                return c < B.c;
            else
                return b < B.b;
        }
        return a < B.a;
    }
};

map <node,bool> Map;

node V[N];

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        node tmp = {u,v,w};
        Map[ tmp ] = 1;
        V[i] = {u,v,w};
    }
    for(int i=1;i<=m;i++){
        int a = V[i].a,b = V[i].b,c = V[i].c;
        for(int d=1;d<=n;d++){
            if(d == a || d == b || d == c ) continue;
            if(!Map[(node){a,b,d}]) continue;
            if(!Map[(node){a,c,d}]) continue;
            if(!Map[(node){b,c,d}]) continue;
            ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}

提交记录

2024/8/26 16:29
加载中...