結果

問題 No.2072 Anatomy
ユーザー ___Johniel
提出日時 2022-10-05 19:25:08
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 45 ms / 2,000 ms
コード長 3,061 bytes
コンパイル時間 1,624 ms
コンパイル使用メモリ 172,160 KB
実行使用メモリ 7,296 KB
最終ジャッジ日時 2025-01-01 20:44:12
合計ジャッジ時間 4,907 ms
ジャッジサーバーID
(参考情報)
judge3 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

// github.com/Johniel/contests
// yukicoder/2072/main.cpp
#include <bits/stdc++.h>
#define each(i, c) for (auto& i : c)
#define unless(cond) if (!(cond))
// #define endl "\n"
using namespace std;
template<typename P, typename Q> ostream& operator << (ostream& os, pair<P, Q> p) { os << "(" << p.first << "," << p.second << ")"; return os; }
template<typename P, typename Q> istream& operator >> (istream& is, pair<P, Q>& p) { is >> p.first >> p.second; return is; }
template<typename T> ostream& operator << (ostream& os, vector<T> v) { os << "("; for (auto& i: v) os << i << ","; os << ")"; return os; }
template<typename T> istream& operator >> (istream& is, vector<T>& v) { for (auto& i: v) is >> i; return is; }
template<typename T> ostream& operator << (ostream& os, set<T> s) { os << "#{"; for (auto& i: s) os << i << ","; os << "}"; return os; }
template<typename K, typename V> ostream& operator << (ostream& os, map<K, V> m) { os << "{"; for (auto& i: m) os << i << ","; os << "}"; return os; }
template<typename E, size_t N> istream& operator >> (istream& is, array<E, N>& a) { for (auto& i: a) is >> i; return is; }
template<typename E, size_t N> ostream& operator << (ostream& os, array<E, N>& a) { os << "[]{"; for (auto& i: a) os << i << ","; os << "}"; return os
    ; }
template<typename T> inline T setmax(T& a, T b) { return a = std::max(a, b); }
template<typename T> inline T setmin(T& a, T b) { return a = std::min(a, b); }
using lli = long long int;
using ull = unsigned long long;
using str = string;
template<typename T> using vec = vector<T>;
constexpr array<int, 8> di({0, 1, -1, 0, 1, -1, 1, -1});
constexpr array<int, 8> dj({1, 0, 0, -1, 1, -1, -1, 1});
constexpr lli mod = 1e9 + 7;
// constexpr lli mod = 998244353;
class UnionFind {
public:
UnionFind(int n) {
r.resize(n, 0);
p.resize(n, -1);
}
void unite(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return ;
if (r[a] > r[b]) {
p[a] += p[b];
p[b] = a;
} else {
p[b] += p[a];
p[a] = b;
if(r[a] == r[b]) r[b]++;
}
return ;
}
int find(int a) {
return (p[a] < 0) ? a : p[a] = find(p[a]);
}
bool same(int a, int b) {
return find(a) == find(b);
}
size_t size(int n) {
return -p.at(find(n));
}
private:
vector<int> r, p;
};
int main(int argc, char *argv[])
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.setf(ios_base::fixed);
cout.precision(15);
int n, m;
while (cin >> n >> m) {
vec<pair<int, int>> v(m);
cin >> v;
each (i, v) --i.first, --i.second;
reverse(v.begin(), v.end());
UnionFind uf(n);
int w[n];
fill(w, w + n, 0);
each (e, v) {
if (uf.same(e.first, e.second)) {
++w[uf.find(e.first)];
} else {
int x = max(w[uf.find(e.first)], w[uf.find(e.second)]) + 1;
uf.unite(e.first, e.second);
uf.find(e.first);
uf.find(e.second);
w[uf.find(e.first)] = w[uf.find(e.second)] = x;
}
}
cout << *max_element(w, w + n) << endl;
}
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0