結果

問題 No.1639 最小通信路
ユーザー ゆきのん
提出日時 2021-08-06 21:49:35
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 17 ms / 2,000 ms
コード長 1,992 bytes
コンパイル時間 1,959 ms
コンパイル使用メモリ 193,956 KB
最終ジャッジ日時 2025-01-23 15:04:00
ジャッジサーバーID
（参考情報） 		judge5 / judge6
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 43
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
//#include<atcoder/all>
//#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
//using namespace atcoder;
//using namespace boost::multiprecision;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long ll;
typedef pair<ll,ll> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T> T gcd(T a,T b){return b?gcd(b,a%b):a;}
const ll mod=1e9 + 7;
const ll LINF=1ll<<60;
const int INF=1<<30;
//int dx[]={0,1,0,-1,0,1,-1,1,-1};
//int dy[]={0,0,1,0,-1,1,-1,-1,1};
int dx[]={0,0,1,-1};
int dy[]={-1,1,0,0};


const int M_N=200001;

struct edge { int from;int to;ll cost;
    bool operator<(const edge &right)const{ return right.cost<cost;}
};

struct UnionFind{
    int par[M_N];
    int rank[M_N];

    void init(int n){
        for(int i=0;i<n;i++){
            par[i]=i;
            rank[i]=0;
        }
    }

    int find(int x){
        if(par[x]==x){
            return x;
        }
        else{
            return par[x]=find(par[x]);
        }
    }

    void unite(int x,int y){
        x=find(x);
        y=find(y);
        if(x==y) return;
        if(rank[x]<rank[y]){
            par[x]=y;
        }
        else{
            par[y]=x;
            if(rank[x]==rank[y]) rank[x]++;
        }
    }

    bool same(int x,int y){
        return find(x)==find(y);
    }
};


int main(){
    int n;cin >> n;
    UnionFind uf; 
    uf.init(n);
    int cnt = 0;
    for (int i = 0; i < n * (n - 1) / 2; i++) {
        int x,y;cin >> x >> y;
        x--,y--;
        string c;cin >> c;
        if(uf.same(x, y)) continue;
        uf.unite(x, y);
        cnt++;
        if(cnt == n - 1){
            cout << c << endl;
            return 0;
        }
    }
    return 0;
}
0