Submission #8320293
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for(int i = int(a), i##_len = (b); i < i##_len; ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define _repr(i, n) repri(i, n, 0)
/* loop in [n,m] step -1 */
#define repri(i, a, b) for(int i = int(a), i##_len = (b); i >= i##_len; --i)
/* loop in [n,0] step -1 or [n,m] step -1 */
#define repr(...) _overload3(__VA_ARGS__, repri, _repr, )(__VA_ARGS__)
#define all(x) (x).begin(), (x).end()
#define debug(x) cerr << #x << ": " << (x) << '\n'
#define endl '\n'
typedef vector<int> vint;
typedef pair<int, int> pint;
#define CPP_STR(x) CPP_STR_I(x)
#define CPP_CAT(x, y) CPP_CAT_I(x, y)
#define CPP_STR_I(args...) #args
#define CPP_CAT_I(x, y) x##y
#define ASSERT(expr...) assert((expr))
/* type annotation */
using i8 = int8_t;
using u8 = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
using f32 = float;
using f64 = double;
constexpr i64 INF = 1'010'000'000'000'000'017LL;
constexpr i64 MOD = 1'000'000'007LL;
constexpr f64 EPS = 1e-12;
constexpr f64 PI = 3.14159265358979323846;
/* macros */
#define FOR(i, start, end) \
for(i64 i = (start), CPP_CAT(i, xxxx_end) = (end); \
i < CPP_CAT(i, xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(f, c, ...) \
(([&](decltype((c)) cccc) { \
return (f)(std::begin(cccc), std::end(cccc), ##__VA_ARGS__); \
})(c))
template <typename C>
i64 SIZE(const C &c) {
return static_cast<i64>(c.size());
}
template <typename T, size_t N>
i64 SIZE(const T (&)[N]) {
return static_cast<i64>(N);
}
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
/* marathon match */
#ifdef LOCAL
const i64 CYCLES_PER_SEC = 2800000000;
#else
const i64 CYCLES_PER_SEC = 2800000000; // AtCoder
#endif
struct Timer {
i64 start;
Timer() { reset(); }
void reset() { start = getCycle(); }
inline double get() {
return (double)(getCycle() - start) / CYCLES_PER_SEC * 1000;
}
private:
inline i64 getCycle() {
u32 low, high;
__asm__ volatile("rdtsc" : "=a"(low), "=d"(high));
return ((i64)low) | ((i64)high << 32);
}
} timer;
class XorShift {
public:
unsigned int x, y, z, w;
double nL[65536];
XorShift() { init(); }
void init() {
x = 314159265;
y = 358979323;
z = 846264338;
w = 327950288;
double n = 1 / (double)(2 * 65536);
for(int i = 0; i < 65536; i++) {
nL[i] = log(((double)i / 65536) + n);
}
}
inline unsigned int next() {
unsigned int t = x ^ x << 11;
x = y;
y = z;
z = w;
return w = w ^ w >> 19 ^ t ^ t >> 8;
}
inline double nextLog() { return nL[next() & 0xFFFF]; }
inline int nextInt(int m) { return (int)(next() % m); }
int nextInt(int min, int max) { return min + nextInt(max - min + 1); }
inline double nextDouble() { return (double)next() / ((long long)1 << 32); }
} rnd;
struct IoSetup {
IoSetup() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
cout << fixed << setprecision(20);
cerr << fixed << setprecision(20);
}
} iosetup;
/* lambda recursion */
template <typename F>
class
#if defined(__has_cpp_attribute) && __has_cpp_attribute(nodiscard)
[[nodiscard]]
#elif defined(__GNUC__) && __GNUC_PREREQ(3, 4)
__attribute__((warn_unused_result))
#endif // defined(__has_cpp_attribute) && __has_cpp_attribute(nodiscard)
FixPoint :
F { public : explicit constexpr FixPoint(F &&f) noexcept :
F(std::forward<F>(f)) {}
template <typename... Args> constexpr decltype(auto)
operator()(Args &&... args) const {
return F::operator()(*this, std::forward<Args>(args)...);
}
}
; // class FixPoint
template <typename F>
static inline constexpr decltype(auto) makeFixPoint(F &&f) noexcept {
return FixPoint<F>{std::forward<F>(f)};
}
/* keep a max,min */
template <typename T, typename U, typename Comp = less<>>
bool chmax(T &xmax, const U &x, Comp comp = {}) {
if(comp(xmax, x)) {
xmax = x;
return true;
}
return false;
}
template <typename T, typename U, typename Comp = less<>>
bool chmin(T &xmin, const U &x, Comp comp = {}) {
if(comp(x, xmin)) {
xmin = x;
return true;
}
return false;
}
/* input,output operator for pair, vector and map */
template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
os << "(" << p.first << ", " << p.second << ")";
return os;
}
template <typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p) {
is >> p.first >> p.second;
return is;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
os << "[";
for(int i = 0; i < (int)v.size(); i++) {
os << v[i] << (i + 1 != v.size() ? ", " : "");
}
os << "]";
return os;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &v) {
for(T &in : v) is >> in;
return is;
}
template <typename T, typename U>
ostream &operator<<(ostream &os, const map<T, U> &mp) {
for(auto x = mp.begin(); x != mp.end(); ++x) {
os << x->first << ": " << x->second
<< (x != prev(mp.end()) ? "\n" : "");
}
return os;
}
/* initialize vector. usage: auto v = make_v<int>(N,0); */
template <typename T>
vector<T> make_v(size_t a) {
return vector<T>(a);
}
template <typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
/* fill vector. usage: fill_v(v,0); */
template <typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type fill_v(T &t, const V &v) {
t = v;
}
template <typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type fill_v(T &t, const V &v) {
for(auto &e : t) fill_v(e, v);
}
/* sum */
template <typename T>
T sum(vector<T> &v) {
T ret = 0;
for(T x : v) {
ret += x;
}
return ret;
}
template <typename T>
auto sum(const T &a) {
return a;
}
template <typename T, typename... A>
auto sum(const T &first, const A &... rest) {
return sum(first) + sum(rest...);
}
/* UnionFind */
struct UnionFind {
int n, num;
vector<int> r, p;
UnionFind() {}
UnionFind(int sz) : n(sz), num(sz), r(sz, 1), p(sz, 0) {
iota(p.begin(), p.end(), 0);
}
int root(int x) { return (x == p[x] ? x : p[x] = root(p[x])); }
bool same(int x, int y) { return root(x) == root(y); }
void unite(int x, int y) {
x = root(x);
y = root(y);
if(x == y) return;
if(r[x] < r[y]) swap(x, y);
r[x] += r[y];
p[y] = x;
num--;
}
int size(int x) { return r[root(x)]; }
int count() const { return num; }
};
int main() {
i64 N, M;
cin >> N >> M;
vector<i64> p(N);
REP(i, N) {
i64 t;
cin >> t;
t--;
p[i] = t;
}
UnionFind uf(N);
REP(i, M) {
i64 a, b;
cin >> a >> b;
uf.unite(a - 1, b - 1);
}
i64 ans = 0;
REP(i, N) {
i64 t = p[i];
if(uf.same(t, i)) ans++;
}
cout << ans << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
D - Equals |
User |
edamat |
Language |
C++14 (GCC 5.4.1) |
Score |
400 |
Code Size |
7808 Byte |
Status |
AC |
Exec Time |
32 ms |
Memory |
2304 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
400 / 400 |
Status |
|
|
Set Name |
Test Cases |
Sample |
0_000.txt, 0_001.txt, 0_002.txt, 0_003.txt |
All |
0_000.txt, 0_001.txt, 0_002.txt, 0_003.txt, 1_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt, 1_018.txt, 1_019.txt, 1_020.txt, 1_021.txt, 1_022.txt |
Case Name |
Status |
Exec Time |
Memory |
0_000.txt |
AC |
3 ms |
768 KB |
0_001.txt |
AC |
3 ms |
768 KB |
0_002.txt |
AC |
3 ms |
768 KB |
0_003.txt |
AC |
3 ms |
768 KB |
1_004.txt |
AC |
17 ms |
768 KB |
1_005.txt |
AC |
27 ms |
2304 KB |
1_006.txt |
AC |
32 ms |
2304 KB |
1_007.txt |
AC |
3 ms |
768 KB |
1_008.txt |
AC |
3 ms |
768 KB |
1_009.txt |
AC |
3 ms |
768 KB |
1_010.txt |
AC |
3 ms |
768 KB |
1_011.txt |
AC |
3 ms |
768 KB |
1_012.txt |
AC |
3 ms |
768 KB |
1_013.txt |
AC |
3 ms |
768 KB |
1_014.txt |
AC |
4 ms |
768 KB |
1_015.txt |
AC |
3 ms |
768 KB |
1_016.txt |
AC |
3 ms |
768 KB |
1_017.txt |
AC |
4 ms |
768 KB |
1_018.txt |
AC |
15 ms |
768 KB |
1_019.txt |
AC |
12 ms |
2304 KB |
1_020.txt |
AC |
12 ms |
2304 KB |
1_021.txt |
AC |
12 ms |
2304 KB |
1_022.txt |
AC |
32 ms |
2304 KB |