Submission #7355195
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
#define LOOP(N) for(int i=(int)(N); i--;)
#define REP(i, N) for(int i=0; i<(N); ++i)
#define FOR(i, start, end) for(int i=(int)(start); i<(end); ++i)
#define ALL(a) (a).begin(),(a).end()
class UnionFind {
vector<int> parent;
int rank(int v) {
// 根でしか呼び出していないのでこの実装
// 根以外でも呼び出す場合は、-parent[getRoot(v)]とする。
return -parent[v];
}
public:
UnionFind(int N) : parent(N, -1) {}
int getRoot(int v) {
return parent[v] < 0 ? v : parent[v] = getRoot(parent[v]);
}
void unite(int a, int b) {
a = getRoot(a);
b = getRoot(b);
if (a == b) return;
if (rank(a) < rank(b)) swap(a, b);
parent[a] += parent[b];
parent[b] = a;
}
bool isSameGroup(int a, int b) {
return getRoot(a) == getRoot(b);
}
};
class FastIO {
static const int BUF_SIZE = 1<<17;
char inBuf[BUF_SIZE + 2];
char *in, *inEnd = inBuf + BUF_SIZE;
char outBuf[BUF_SIZE + 2];
char *out, *outEnd = outBuf + BUF_SIZE;
// stdinからBUFFER_SIZE分まで一気に読み込み、読み込んだサイズを返す
size_t Load() {
in = inBuf;
size_t size = fread(inBuf, 1, BUF_SIZE, stdin);
inBuf[size] = '\0';
return size;
}
// lenの長さの文字列を出力した場合にバッファを超過するなら、バッファをリセットする
void FlushIfNeed(int len) {
if (out + len > outEnd) flush();
}
// lenの長さの文字列を入力した場合にバッファを超過するなら、バッファをリロードする
void LoadIfNeed(int len) {
if (in + len <= inEnd) return;
int rest_size = inEnd - in;
memcpy(inBuf, in, rest_size);
size_t size = fread(inBuf + rest_size, 1, BUF_SIZE - rest_size, stdin);
inBuf[rest_size + size] = '\0';
in = inBuf;
}
char GetChar() {
if (*in == '\0') {
// これ以上読み込みできなかった場合はとりあえず0を返しておく
if (Load() == 0) return 0;
}
return *in++;
}
void PutChar(char c) {
FlushIfNeed(1);
*out++ = c;
}
// 0以上の整数向けのscan
template<typename T>
void ScanNatural(T &x) {
x = 0;
// 数字が出てくるまでスキップ
char c = GetChar();
while(!isdigit(c)) c = GetChar();
// 数値に変換
LoadIfNeed(21);
x = c&15;
for (c = *in++; isdigit(c); c = *in++) {
// c = '0'~'9' = 48~57 のとき、 c & 15 = c - '0'
x = x * 10 + (c&15);
}
}
// 負数を考慮する整数値scan
template<typename T>
void ScanInteger(T &x) {
x = 0;
// -記号か数字が出てくるまでスキップ
char c = GetChar();
while (c != '-' && !isdigit(c)) c = GetChar();
// -記号の処理
bool minus = c == '-';
if (minus) c = GetChar();
LoadIfNeed(21);
x = c&15;
for (c = *in++; isdigit(c); c = *in++) {
x = x * 10 + (c&15);
}
if (minus) x = -x;
}
// 長さの分かっている文字列の出力(lenはBUFFER_SIZE以下)
void PrintString(const char *s, size_t len) {
char *new_out_pos = out + len;
if (new_out_pos > outEnd) {
flush();
new_out_pos = out + len;
}
memcpy(out, s, len);
out = new_out_pos;
}
// 非負整数値の出力
template<typename T>
void PrintNatural(T x) {
char digit[20], *d_start, *d_end;
d_start = d_end = digit + 32;
// x = 0 の場合も0を出力する必要があるので、do whileで最低1桁は処理する
do {
// 上の桁に向かって処理していくので、表示順序と逆になる
--d_start;
*d_start = x % 10 + '0';
x /= 10;
} while (x != 0);
// 出力
PrintString(d_start, d_end - d_start);
}
// 整数値の出力
template<typename T>
void PrintInteger(T x) {
if (x < 0) {
PutChar('-');
x = -x;
}
PrintNatural(x);
}
public:
// 出力バッファの中身をstdoutに流し出し、出力バッファをリセットする
void flush() {
fwrite(outBuf, out - outBuf, 1, stdout);
out = outBuf;
}
FastIO() {
Load();
out = outBuf;
}
~FastIO() {flush();}
void scan(string &s) {
char c = GetChar();
while (!isprint(c)) c = GetChar();
s.clear();
for (; isprint(c); c = GetChar()) {
s.push_back(c);
}
}
void scan(ll &x) {ScanInteger(x);}
void scan(int &x) {ScanInteger(x);}
void scan(ull &x) {ScanNatural(x);}
void scan(uint &x) {ScanNatural(x);}
template<typename First, typename ... Ints>
void scan(First &arg, Ints&... rest) {
scan(arg);
scan(rest...);
}
void print(const char *s) {
size_t len = strlen(s);
// バッファサイズより大きい文字列を出力しようとした場合は、stdoutにそのまま流す
if (len > BUF_SIZE) {
flush();
printf("%s", s);
return;
}
PrintString(s, len);
}
void print(string &s) {PrintString(s.c_str(), s.size());}
void print(ll x) {PrintInteger(x);}
void print(int x) {PrintInteger(x);}
void print(ull x) {PrintNatural(x);}
void print(uint x) {PrintNatural(x);}
template<typename First, typename ... Ints>
void print(First &arg, Ints&... rest) {
print(arg);
PutChar(' ');
print(rest...);
}
template <typename T>
void printl(T t) {
print(t);
PutChar('\n');
}
template <typename First, typename ... Ints>
void printl(First &arg, Ints&... rest) {
print(arg);
PutChar(' ');
printl(rest...);
}
void SayYes() {
PrintString("Yes\n", 4);
}
void SayNo() {
PrintString("No\n", 3);
}
};
int main() {
FastIO io;
int N, Q;
io.scan(N, Q);
UnionFind unf(N);
uint p, a, b;
REP(i, Q) {
io.scan(p, a, b);
// conbine
if (p == 0) {
unf.unite(a, b);
}
// judge
else {
if (unf.isSameGroup(a, b)) io.SayYes();
else io.SayNo();
}
}
}
Submission Info
Submission Time |
|
Task |
B - Union Find |
User |
scientistb |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
6972 Byte |
Status |
AC |
Exec Time |
7 ms |
Memory |
1408 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
100 / 100 |
Status |
|
|
Set Name |
Test Cases |
Sample |
00_sample_01.txt |
All |
00_sample_01.txt, subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_01_18.txt |
Case Name |
Status |
Exec Time |
Memory |
00_sample_01.txt |
AC |
1 ms |
256 KB |
subtask_01_01.txt |
AC |
4 ms |
896 KB |
subtask_01_02.txt |
AC |
1 ms |
640 KB |
subtask_01_03.txt |
AC |
4 ms |
1280 KB |
subtask_01_04.txt |
AC |
6 ms |
1408 KB |
subtask_01_05.txt |
AC |
1 ms |
384 KB |
subtask_01_06.txt |
AC |
2 ms |
768 KB |
subtask_01_07.txt |
AC |
6 ms |
1024 KB |
subtask_01_08.txt |
AC |
6 ms |
1408 KB |
subtask_01_09.txt |
AC |
1 ms |
256 KB |
subtask_01_10.txt |
AC |
1 ms |
640 KB |
subtask_01_11.txt |
AC |
5 ms |
1152 KB |
subtask_01_12.txt |
AC |
6 ms |
1408 KB |
subtask_01_13.txt |
AC |
5 ms |
1024 KB |
subtask_01_14.txt |
AC |
1 ms |
640 KB |
subtask_01_15.txt |
AC |
5 ms |
1024 KB |
subtask_01_16.txt |
AC |
6 ms |
1408 KB |
subtask_01_17.txt |
AC |
7 ms |
1152 KB |
subtask_01_18.txt |
AC |
7 ms |
1152 KB |