CODE FESTIVAL 2016 Final

Submission #992589

Source codeソースコード

import std.stdio;
import std.string;
import std.conv;
import std.typecons;
import std.algorithm;
import std.functional;
import std.bigint;
import std.numeric;
import std.array;
import std.math;
import std.range;
import std.container;
import std.ascii;
void times(alias pred)(int n) {
    foreach(i; 0..n) pred();
}
auto rep(alias pred, T = typeof(pred()))(int n) {
    T[] res = new T[n];
    foreach(ref e; res) e = pred();
    return res;
}

void main() {
  int N, M;
  readf("%d %d\n", &N, &M);

  auto set = DisjointSet(N);
  int[] ary = M.rep!(() => -1);
  foreach(i; 0..N) {
    readln.split[1..$].to!(int[]).map!"a-1".each!((j) {
      if (ary[j] >=0) set.unite(ary[j], i);
      ary[j] = i;
    });
  }

  size_t[] res = N.iota.map!(i => set.findSet(i)).array;
  writeln(res.all!(a => a==res.front) ? "YES":"NO");
}

// 互いに素な集合
// UnionFindTreeによる実装
struct DisjointSet {

private:
    Vertex[] _vertices;

public:
    this(size_t size) {
        _vertices = new Vertex[size];
        foreach(i, ref v; _vertices) {
            v.index = i;
            v.parent = i;
        }
    }

    void makeSet(size_t[] indices...) {
        foreach(index; indices) {
            _vertices[index] = Vertex(index, index);
        }
    }

    void unite(size_t x, size_t y) {
        link(findSet(x), findSet(y));
    }

    void link(size_t x, size_t y) {
        if (x==y) return;
        if (_vertices[x].rank > _vertices[y].rank) {
            _vertices[y].parent = x;
        } else {
            _vertices[x].parent = y;
            if (_vertices[x].rank == _vertices[y].rank) {
                _vertices[y].rank++;
            }
        }
    }

    bool same(size_t x, size_t y) {
        return findSet(x) == findSet(y);
    }

    size_t findSet(size_t index) {
        if (_vertices[index].parent == index) {
            return index;
        } else {
            return _vertices[index].parent = findSet(_vertices[index].parent);
        }
    }

private:
    struct Vertex {
        size_t index;
        size_t parent;
        size_t rank = 1;
    }
}

Submission

Task問題 C - Interpretation
User nameユーザ名 Ark
Created time投稿日時
Language言語 D (DMD64 v2.070.1)
Status状態 AC
Score得点 400
Source lengthソースコード長 2182 Byte
File nameファイル名
Exec time実行時間 100 ms
Memory usageメモリ使用量 4732 KB

Test case

Set

Set name Score得点 / Max score Cases
sample - sample-01.txt,sample-02.txt
dataset1 200 / 200 sample-01.txt,sample-02.txt,01-01.txt,01-02.txt,01-03.txt,01-04.txt,01-05.txt,01-06.txt,01-07.txt,01-08.txt,01-09.txt,01-10.txt
dataset2 200 / 200 sample-01.txt,sample-02.txt,01-01.txt,01-02.txt,01-03.txt,01-04.txt,01-05.txt,01-06.txt,01-07.txt,01-08.txt,01-09.txt,01-10.txt,02-01.txt,02-02.txt,02-03.txt,02-04.txt,02-05.txt,02-06.txt,02-07.txt,02-08.txt,02-09.txt,02-10.txt,02-11.txt,02-12.txt,02-13.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
01-01.txt AC 2 ms 256 KB
01-02.txt AC 2 ms 380 KB
01-03.txt AC 3 ms 508 KB
01-04.txt AC 3 ms 508 KB
01-05.txt AC 3 ms 508 KB
01-06.txt AC 3 ms 380 KB
01-07.txt AC 3 ms 380 KB
01-08.txt AC 3 ms 380 KB
01-09.txt AC 3 ms 380 KB
01-10.txt AC 3 ms 508 KB
02-01.txt AC 28 ms 1788 KB
02-02.txt AC 95 ms 4348 KB
02-03.txt AC 33 ms 1788 KB
02-04.txt AC 71 ms 3452 KB
02-05.txt AC 86 ms 3836 KB
02-06.txt AC 71 ms 3452 KB
02-07.txt AC 95 ms 4092 KB
02-08.txt AC 92 ms 4348 KB
02-09.txt AC 100 ms 4732 KB
02-10.txt AC 60 ms 4100 KB
02-11.txt AC 60 ms 3936 KB
02-12.txt AC 59 ms 3068 KB
02-13.txt AC 59 ms 3068 KB
sample-01.txt AC 2 ms 256 KB
sample-02.txt AC 2 ms 256 KB