CODE FESTIVAL 2016 Final (Parallel)

Submission #1348931

Source codeソースコード

//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
#define MOD 1000000007
#define INF (1LL<<30)
#define LLINF (1LL<<60)
#define PI 3.14159265359
#define EPS 1e-12
//#define int ll

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

#define MAX_N 200000

class UnionFind {
private:
  // 親と木の深さ
  int par[MAX_N];
  int rank[MAX_N];
  int s[MAX_N];
public:
  void init(int n);
  int find(int x);
  void unite(int x, int y);
  bool same(int x, int y);
};

// 要素数nで初期化
void UnionFind::init (int n) {
  for(int i=0; i<n; i++) {
    par[i] = i;
    rank[i] = 0;
    s[i] = 1;
  }
}

// 要素xの親を求める
int UnionFind::find(int x) {
  if(par[x] == x) return x;
  else return par[x] = find(par[x]);
}

// xとyの属する集合を併合
void UnionFind::unite(int x, int y) {
  // xとyの親
  x = find(x);
  y = find(y);
  if(x == y) return;

  // yのほうが深さが深い xの親はyの親
  if(rank[x] < rank[y]) {
    par[x] = y;
    s[y] = s[x] + s[y];
  }
  else {
    par[y] = x;
    s[x] = s[x] + s[y];
    if( rank[x] == rank[y] ) rank[x]++;
  }
}

// xとyが同じ集合に属するか
bool UnionFind::same(int x, int y) { return find(x) == find(y);}

UnionFind uf;
VI v[100010];
signed main(void)
{
	int n, m;
	cin >> n >> m;
	uf.init(n+1);
	REP(i, n) {
		int k;
		cin >> k;
		REP(j, k) {
			int l;
			cin >> l;
			v[l-1].PB(i);
		}
	}

	REP(i, m) {
		//cout << "i:" << i << endl;
		//for(int j: v[i]) cout << j << " "; cout << endl;
		REP(j, v[i].size()-1) {
			//cout << v[i][j] << " " << v[i][j+1] << endl;
			uf.unite(v[i][j], v[i][j+1]);
		}
		//REP(j, n) cout << uf.find(j) << " "; cout << endl;
	}
	REP(i, n-1) {
		//cout << uf.find(i) << " " << uf.find(i+1) << endl;
		if(!uf.same(i, i+1)) {cout << "NO" << endl; return 0;}
	}
	cout << "YES" << endl;

	return 0;
}

Submission

Task問題 C - Interpretation
User nameユーザ名 ferin
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 400
Source lengthソースコード長 2300 Byte
File nameファイル名
Exec time実行時間 58 ms
Memory usageメモリ使用量 6272 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,sample-01.txt,sample-02.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
01-01.txt AC 3 ms 4352 KB
01-02.txt AC 3 ms 4352 KB
01-03.txt AC 3 ms 4352 KB
01-04.txt AC 3 ms 4352 KB
01-05.txt AC 3 ms 4352 KB
01-06.txt AC 3 ms 4352 KB
01-07.txt AC 3 ms 4352 KB
01-08.txt AC 3 ms 4352 KB
01-09.txt AC 3 ms 4352 KB
01-10.txt AC 3 ms 4352 KB
02-01.txt AC 48 ms 6272 KB
02-02.txt AC 49 ms 5120 KB
02-03.txt AC 48 ms 5760 KB
02-04.txt AC 58 ms 5760 KB
02-05.txt AC 55 ms 5248 KB
02-06.txt AC 58 ms 5760 KB
02-07.txt AC 57 ms 5248 KB
02-08.txt AC 39 ms 5120 KB
02-09.txt AC 58 ms 5116 KB
02-10.txt AC 51 ms 6144 KB
02-11.txt AC 50 ms 6144 KB
02-12.txt AC 50 ms 6016 KB
02-13.txt AC 50 ms 6016 KB
sample-01.txt AC 3 ms 4352 KB
sample-02.txt AC 3 ms 4352 KB