Submission #1172895
Source Code Expand
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstddef>
class FastIO {
// output buffer must be larger than each output
static const size_t BUF_SIZE=1<<17;
static char inbuf[BUF_SIZE|1], *inptr, *endinbuf;
static char outbuf[BUF_SIZE|1], *outptr, *endoutbuf;
static void weak_flush() {
// flushes the internal buffer but not flushing stdout
fwrite(outbuf, 1, outptr-outbuf, stdout);
outptr = outbuf;
}
static void buffer() {
// reads characters from stdin and buffers
size_t len=fread(inbuf, 1, BUF_SIZE, stdin);
inbuf[len] = '\0';
inptr = inbuf;
}
static void buffer(size_t oft) {
size_t len=fread(inbuf+oft, 1, BUF_SIZE-oft, stdin);
inbuf[oft+len] = '\0';
}
public:
static void scan(double &d) {
char *tmp;
d = strtod(inptr, &tmp);
if (tmp < endinbuf && tmp != inptr) {
// successfully scanned
inptr = tmp;
return;
}
// reachs EOB before/while converting
ptrdiff_t left=endinbuf-inptr;
memcpy(inbuf, inptr, left);
buffer(left);
d = strtod(inbuf, &inptr);
}
static void scan(char &c) {
c = *inptr++;
if (c != '\0') return;
// reaches EOB
buffer();
c = *inptr++;
}
static void scan(char *s) {
char *pos=inptr, *src=pos;
bool started=false;
for (;; ++pos) {
char tmp=*pos;
if (tmp == '\0') {
// unbuffers and rebuffers if reaches EOB
ptrdiff_t count=pos-src;
memcpy(s, src, count);
s += count;
buffer();
pos = src = inbuf;
tmp = *inbuf;
}
if (tmp != ' ' && tmp != '\n') {
// not delimiters
if (!started) {
started = true;
src = pos;
}
} else if (started) {
memcpy(s, src, pos-src);
s[pos-src] = '\0';
inptr = ++pos;
return;
}
// nops until non-delimiter char appears
}
}
template <class Integral>
static void scan(Integral &n) {
bool started=false, neg=false;
n = 0;
for (;;) {
char tmp=*inptr++;
if (tmp == '\0') {
buffer();
tmp = *inptr++;
}
if (tmp >= '0' && tmp <= '9') {
started = true;
n = n*10 + tmp-'0';
} else if (started) {
++tmp;
break;
} else if (std::is_signed<Integral>::value && tmp == '-') {
neg = true;
}
}
if (std::is_signed<Integral>::value && neg) n = -n;
}
template <class Arithmetic, class... Rest>
static void scan(Arithmetic &x, Rest&... y) {
scan(x);
scan(y...);
}
static void print(double d) {
char minibuf[20];
size_t count=snprintf(minibuf, sizeof minibuf, "%.12f", d);
char *tmp=outptr+count;
if (tmp >= endoutbuf) {
weak_flush();
tmp = outbuf+count;
}
memcpy(outptr, minibuf, count);
outptr = tmp;
}
static void print(char c) {
if (outptr+1 >= endoutbuf)
weak_flush();
*outptr++ = c;
}
static void print(const char *s) {
size_t count=strlen(s);
char *tmp=outptr+count;
if (tmp >= endoutbuf) {
weak_flush();
tmp = outbuf + count;
}
memcpy(outptr, s, count);
outptr = tmp;
}
static void print(char *s) {
size_t count=strlen(s);
char *tmp=outptr+count;
if (tmp >= endoutbuf) {
weak_flush();
tmp = outbuf + count;
}
memcpy(outptr, s, count);
outptr = tmp;
}
template <size_t N>
static void print(const char (&s)[N]) {
size_t count=strlen(s);
char *tmp=outptr+count;
if (tmp >= endoutbuf) {
weak_flush();
tmp = outbuf + count;
}
memcpy(outptr, s, count);
outptr = tmp;
}
template <class Integral>
static void print(Integral n) {
if (outptr+20 >= endoutbuf)
weak_flush();
if (n == 0) {
*outptr++ = '0';
return;
}
char minibuf[20], *pos=minibuf+20, *endminibuf=pos;
if (std::is_signed<Integral>::value && n < 0) {
*outptr++ = '-';
n = -n;
}
while (n) {
*--pos = n%10 + '0';
n /= 10;
}
memcpy(outptr, pos, endminibuf-pos);
outptr += endminibuf-pos;
}
template <class T, class... Rest>
static void print(T x, Rest&&... y) {
// prints arguments without separating characters
print(x);
print(y...);
}
template <class T>
static void println(T x) {
print(x, '\n');
}
template <class T, class... Rest>
static void println(T x, Rest&&... y) {
// prints arguments separated by a single space and terminates the line
print(x, ' ');
println(y...);
}
template <class T>
static void printlns(T x) {
print(x, '\n');
}
template <class T, class... Rest>
static void printlns(T x, Rest&&... y) {
// prints each of arguments per line
print(x, '\n');
printlns(y...);
}
static void flush() {
// flushes the buffer
// should be called before main() returns
fwrite(outbuf, 1, outptr-outbuf, stdout);
fflush(stdout);
outptr = outbuf;
}
};
char FastIO::inbuf[], *FastIO::inptr=FastIO::inbuf;
char *FastIO::endinbuf=inbuf+FastIO::BUF_SIZE;
char FastIO::outbuf[], *FastIO::outptr=FastIO::outbuf;
char *FastIO::endoutbuf=outbuf+FastIO::BUF_SIZE;
class UnionFindTree {
std::vector<int> tree;
public:
UnionFindTree(size_t n): tree(n, -1) {}
size_t find_root(size_t v) {
if (tree[v] < 0) return v;
return tree[v] = find_root(tree[v]);
}
bool unite(size_t x, size_t y) {
x = find_root(x);
y = find_root(y);
if (x == y) return false;
if (rank(x) < rank(y)) std::swap(x, y);
tree[x] += tree[y];
tree[y] = x;
return true;
}
bool connected(size_t x, size_t y) {
return find_root(x) == find_root(y);
}
size_t rank(size_t v) {
return -tree[find_root(v)];
}
};
int main() {
size_t N;
int Q;
FastIO::scan(N, Q);
UnionFindTree tree(N);
for (; Q--;) {
int P;
size_t A, B;
FastIO::scan(P, A, B);
if (P) {
FastIO::print(tree.connected(A, B)? "Yes\n":"No\n");
} else {
tree.unite(A, B);
}
}
FastIO::flush();
return 0;
}
Submission Info
Submission Time |
|
Task |
B - Union Find |
User |
rsk0315 |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
7073 Byte |
Status |
AC |
Exec Time |
8 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 |
5 ms |
1280 KB |
subtask_01_04.txt |
AC |
8 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 |
7 ms |
1024 KB |
subtask_01_08.txt |
AC |
8 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 |
8 ms |
1408 KB |
subtask_01_13.txt |
AC |
6 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 |
8 ms |
1408 KB |
subtask_01_17.txt |
AC |
8 ms |
1152 KB |
subtask_01_18.txt |
AC |
8 ms |
1152 KB |