LeetCode Biweekly Contest 3 3問目 - The Earliest Moment When Everyone Become Friends [1101]

Source

LeetCode Biweekly Contest 3
問題文

問題概要

省略

解法

省略

cLayversion 20190630-1)のコード [C++に変換後]

#include<bits/stdc++.h>
using namespace std;
void *wmem;
struct unionFind{
  int M, N, *d;
  inline void malloc(const int n){
    d = (int*)std::malloc(n*sizeof(int));
    M = n;
  }
  inline void free(void){
    std::free(d);
  }
  inline void walloc(const int n, void **mem=&wmem){
    d = (int*)(*mem);
    (*mem) = (d+n);
    M = n;
  }
  inline void init(const int n){
    int i;
    N = n;
    for(i=0;i<n;i++){
      d[i] = -1;
    }
  }
  inline void init(void){
    init(M);
  }
  inline int get(int a){
    int k, t=a;
    while(d[t]>=0){
      t=d[t];
    }
    while(d[a]>=0){
      k=d[a];
      d[a]=t;
      a=k;
    }
    return a;
  }
  inline int connect(int a, int b){
    if(d[a]>=0){
      a=get(a);
    }
    if(d[b]>=0){
      b=get(b);
    }
    if(a==b){
      return 0;
    }
    if(d[a] < d[b]){
      d[a] += d[b];
      d[b] = a;
    }
    else{
      d[b] += d[a];
      d[a] = b;
    }
    return 1;
  }
  inline int operator()(int a){
    return get(a);
  }
  inline int operator()(int a, int b){
    return connect(a,b);
  }
  inline int& operator[](const int a){
    return d[a];
  }
  inline int sizeList(int res[]){
    int i, sz=0;
    for(i=0;i<N;i++){
      if(d[i]<0){
        res[sz++] = -d[i];
      }
    }
    return sz;
  }
}
;
char memarr[96000000];
int main2(){
  wmem = memarr;
  return 0;
}
struct Solution{
  public:
  int earliestAcq(vector<vector<int>>& logs, int N){
    main2();
    int i, rem=N-1;
    unionFind uf;
    uf.malloc(N);
    uf.init(N);
    sort(logs.begin(), logs.end());
    for(i=0;i<logs.size();i++){
      rem -= uf(logs[i][1], logs[i][2]);
      if(rem==0){
        return logs[i][0];
      }
    }
    return -1;
  }
}
;
// cLay varsion 20190630-1

// --- original code ---
// struct Solution {
// public:
//   int earliestAcq(vector<vector<int>>& logs, int N) {
//     int i, rem = N-1;
//     unionFind uf;
//     uf.malloc(N);
//     uf.init(N);
//     sort(logs.begin(), logs.end());
//     
//     rep(i,logs.size()){
//       rem -= uf(logs[i][1], logs[i][2]);
//       if(rem==0) return logs[i][0];
//     }
//     return -1;
//   }
// };
// 
// {
//   // main関数を適当に処理する
// }

Current time: 2024年03月30日00時24分28秒
Last modified: 2019年06月30日03時07分02秒 (by laycrs)
Tags: Competitive_Programming_Incomplete LeetCode
トップページに戻る

Logged in as: unknown user (not login)

ログイン: