結果
| 問題 | No.2290 UnUnion Find |
| ユーザー |
👑  rin204
|
| 提出日時 | 2023-05-05 21:25:31 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 61 ms / 2,000 ms |
| コード長 | 8,505 bytes |
| コンパイル時間 | 3,529 ms |
| コンパイル使用メモリ | 260,452 KB |
| 実行使用メモリ | 6,400 KB |
| 最終ジャッジ日時 | 2024-11-23 05:54:43 |
| 合計ジャッジ時間 | 10,951 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 46 |
コンパイルメッセージ
In member function 'int UnionFind::find(int)',
inlined from 'bool UnionFind::same(int, int)' at main.cpp:261:31,
inlined from 'void solve()' at main.cpp:315:30:
main.cpp:244:17: warning: 'bv' may be used uninitialized [-Wmaybe-uninitialized]
244 | if(par[x] < 0) return x;
| ^
main.cpp: In function 'void solve()':
main.cpp:282:13: note: 'bv' was declared here
282 | int bu, bv;
| ^~
In member function 'int UnionFind::find(int)',
inlined from 'bool UnionFind::same(int, int)' at main.cpp:261:31,
inlined from 'void solve()' at main.cpp:314:25:
main.cpp:244:17: warning: 'bu' may be used uninitialized [-Wmaybe-uninitialized]
244 | if(par[x] < 0) return x;
| ^
main.cpp: In function 'void solve()':
main.cpp:282:9: note: 'bu' was declared here
282 | int bu, bv;
| ^~
ソースコード
// #pragma GCC target("avx2")// #pragma GCC optimize("O3")// #pragma GCC optimize("unroll-loops")#include<bits/stdc++.h>using namespace std;using ll = long long;using ull = unsigned long long;template <class T>using pq = priority_queue<T>;template <class T>using qp = priority_queue<T, vector<T>, greater<T>>;#define vec(T, A, ...) vector<T> A(__VA_ARGS__);#define vvec(T, A, h, ...) vector<vector<T>> A(h, vector<T>(__VA_ARGS__));#define vvvec(T, A, h1, h2, ...) vector<vector<vector<T>>> A(h1, vector<vector<T>>(h2, vector<T>(__VA_ARGS__)));#ifndef RIN__LOCAL#define endl "\n"#endif#define spa ' '#define len(A) A.size()#define all(A) begin(A), end(A)#define fori1(a) for(ll _ = 0; _ < (a); _++)#define fori2(i, a) for(ll i = 0; i < (a); i++)#define fori3(i, a, b) for(ll i = (a); i < (b); i++)#define fori4(i, a, b, c) for(ll i = (a); ((c) > 0 || i > (b)) && ((c) < 0 || i < (b)); i += (c))#define overload4(a, b, c, d, e, ...) e#define fori(...) overload4(__VA_ARGS__, fori4, fori3, fori2, fori1)(__VA_ARGS__)template <typename T>vector<tuple<ll, T>> ENUMERATE(vector<T> &A, ll s = 0){vector<tuple<ll, T>> ret(A.size());for(int i = 0; i < A.size(); i++) ret[i] = {i + s, A[i]};return ret;}vector<tuple<ll, char>> ENUMERATE(string &A, ll s = 0){vector<tuple<ll, char>> ret(A.size());for(int i = 0; i < A.size(); i++) ret[i] = {i + s, A[i]};return ret;}#define enum1(A) fori(A.size())#define enum2(a, A) for(auto a:A)#define enum3(i, a, A) for(auto&& [i, a]: ENUMERATE(A))#define enum4(i, a, A, s) for(auto&& [i, a]: ENUMERATE(A, s))#define enum(...) overload4(__VA_ARGS__, enum4, enum3, enum2, enum1)(__VA_ARGS__)template <typename T, typename S>vector<tuple<T, S>> ZIP(vector<T> &A, vector<S> &B){int n = min(A.size(), B.size());vector<tuple<T, S>> ret(n);for(int i = 0; i < n; i++) ret[i] = {A[i], B[i]};return ret;}template <typename T, typename S>vector<tuple<ll, T, S>> ENUMZIP(vector<T> &A, vector<S> &B, ll s = 0){int n = min(A.size(), B.size());vector<tuple<ll, T, S>> ret(n);for(int i = 0; i < n; i++) ret[i] = {i + s, A[i], B[i]};return ret;}#define zip4(a, b, A, B) for(auto&& [a, b]: ZIP(A, B))#define enumzip5(i, a, b, A, B) for(auto&& [i, a, b]: ENUMZIP(A, B))#define enumzip6(i, a, b, A, B, s) for(auto&& [i, a, b]: ENUMZIP(A, B, s))#define overload6(a, b, c, d, e, f, g, ...) g#define zip(...) overload6(__VA_ARGS__, enumzip6, enumzip5, zip4, _, _, _)(__VA_ARGS__)vector<char> stoc(string &S){int n = S.size();vector<char> ret(n);for(int i = 0; i < n; i++) ret[i] = S[i];return ret;}#define INT(...) int __VA_ARGS__; inp(__VA_ARGS__);#define LL(...) ll __VA_ARGS__; inp(__VA_ARGS__);#define STRING(...) string __VA_ARGS__; inp(__VA_ARGS__);#define CHAR(...) char __VA_ARGS__; inp(__VA_ARGS__);#define VEC(T, A, n) vector<T> A(n); inp(A);#define VVEC(T, A, n, m) vector<vector<T>> A(n, vector<T>(m)); inp(A);const ll MOD1 = 1000000007;const ll MOD9 = 998244353;template<class T> auto min(const T& a){return *min_element(all(a));}template<class T> auto max(const T& a){return *max_element(all(a));}template <class T, class S>auto clamp(T &a, const S &l, const S &r) {return (a > r ? r : a < l ? l : a);}template <class T, class S>inline bool chmax(T &a, const S &b) {return (a < b ? a = b, 1 : 0);}template <class T, class S>inline bool chmin(T &a, const S &b) {return (a > b ? a = b, 1 : 0);}template <class T, class S>inline bool chclamp(T &a, const S &l, const S &r) {auto b = clamp(a, l, r);return (a != b ? a = b, 1 : 0);}void FLUSH(){cout << flush;}void print(){cout << endl;}template <class Head, class... Tail>void print(Head &&head, Tail &&... tail) {cout << head;if (sizeof...(Tail)) cout << spa;print(forward<Tail>(tail)...);}template<typename T>void print(vector<T> &A){int n = A.size();for(int i = 0; i < n; i++){cout << A[i];if(i != n - 1) cout << ' ';}cout << endl;}template<typename T>void print(vector<vector<T>> &A){for(auto &row: A) print(row);}template<typename T, typename S>void print(pair<T, S> &A){cout << A.first << spa << A.second << endl;}template<typename T, typename S>void print(vector<pair<T, S>> &A){for(auto &row: A) print(row);}template<typename T, typename S>void prisep(vector<T> &A, S sep){int n = A.size();for(int i = 0; i < n; i++){cout << A[i];if(i == n - 1) cout << endl;else cout << sep;}}template<typename T, typename S>void priend(T A, S end){cout << A << end;}template<typename T>void priend(T A){priend(A, spa);}template<class... T>void inp(T&... a){(cin >> ... >> a);}template<typename T>void inp(vector<T> &A){for(auto &a:A) cin >> a;}template<typename T>void inp(vector<vector<T>> &A){for(auto &row:A) inp(row);}template<typename T, typename S>void inp(pair<T, S> &A){inp(A.first, A.second);}template<typename T, typename S>void inp(vector<pair<T, S>> &A){for(auto &row: A) inp(row.first, row.second);}template<typename T>T sum(vector<T> &A){T tot = 0;for(auto a:A) tot += a;return tot;}template<typename T>pair<vector<T>, map<T, int>> compression(vector<T> X){sort(all(X));X.erase(unique(all(X)), X.end());map<T, int> mp;for(int i = 0; i < X.size(); i++) mp[X[i]] = i;return {X, mp};}vector<vector<int>> read_edges(int n, int m, bool direct=false, int indexed=1){vector<vector<int>> edges(n, vector<int>());for(int i = 0; i < m; i++){INT(u, v);u -= indexed;v -= indexed;edges[u].push_back(v);if(!direct) edges[v].push_back(u);}return edges;}vector<vector<int>> read_tree(int n, int indexed=1){return read_edges(n, n - 1, false, indexed);}template<typename T>vector<vector<pair<int, T>>> read_wedges(int n, int m, bool direct=false, int indexed=1){vector<vector<pair<int, T>>> edges(n, vector<pair<int, T>>());for(int i = 0; i < m; i++){INT(u, v);T w;inp(w);u -= indexed;v -= indexed;edges[u].push_back({v, w});if(!direct) edges[v].push_back({u, w});}return edges;}template<typename T>vector<vector<pair<int, T>>> read_wtree(int n, int indexed=1){return read_wedges<T>(n, n - 1, false, indexed);}struct UnionFind{int n;vector<int> par;int group;UnionFind() = default;UnionFind(int n) : n(n){par.assign(n, -1);group = n;}int find(int x){if(par[x] < 0) return x;par[x] = find(par[x]);return par[x];}bool unite(int x, int y){x = find(x);y = find(y);if(x == y) return false;if(par[x] > par[y]) swap(x, y);group--;par[x] += par[y];par[y] = x;return true;}bool same(int x, int y){return find(x) == find(y);}int size(int x){return -par[find(x)];}vector<int> roots(){vector<int> ret;for(int i = 0; i < n; i++){if(i == find(i)) ret.push_back(i);}return ret;}};void solve(){INT(n, Qu);UnionFind UF(n);using P = pair<int, int>;vec(P, Q, Qu);int bu, bv;fori(i, Qu){INT(t);if(t == 1){INT(u, v);u--; v--;Q[i] = {u, v};if(UF.unite(u, v)){bu = u;bv = v;}}else{INT(u);u--;Q[i] = {u, -1};}}if(UF.group >= 2){bu = -1;bv = -1;fori(i, n){if(i == UF.find(i)){if(bu == -1) bu = i;else if(bv == -1) bv = i;}}}UnionFind UF2(n);fori(i, Qu){if(Q[i].second == -1){int u = Q[i].first;if(!UF2.same(u, bu)) print(bu + 1);else if(!UF2.same(u, bv)) print(bv + 1);else print(-1);}else{int u = Q[i].first;int v = Q[i].second;UF2.unite(u, v);}}}int main(){cin.tie(0)->sync_with_stdio(0);// cout << fixed << setprecision(12);int t;t = 1;// cin >> t;while(t--) solve();return 0;}