結果
問題 | No.2290 UnUnion Find |
ユーザー |
|
提出日時 | 2023-05-06 11:40:14 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 502 ms / 2,000 ms |
コード長 | 3,096 bytes |
コンパイル時間 | 4,345 ms |
コンパイル使用メモリ | 259,428 KB |
最終ジャッジ日時 | 2025-02-12 20:31:07 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 46 |
ソースコード
#line 2 "/Users/2P/Desktop/ramstream/library/template/template.hpp" /** * @brief Header */ #include <bits/stdc++.h> // #include <algorithm> // #include <cmath> // #include <complex> // #include <cstdio> // #include <iostream> // #include <map> // #include <numeric> // #include <queue> // #include <set> // #include <stack> // #include <string> // #include <vector> // #include <climits> // #include <deque> // #include <iomanip> // #include <limits> using namespace std; typedef long long ll; #define overload4(_1, _2, _3, _4, name, ...) name #define rep1(i, n) for (int i = 0; i < int(n); ++i) #define rep2(i, s, n) for (int i = int(s); i < int(n); ++i) #define rep3(i, s, n, d) for(int i = int(s); i < int(n); i+=d) #define rep(...) overload4(__VA_ARGS__,rep3,rep2,rep1)(__VA_ARGS__) #define all(x) (x).begin(),(x).end() #define rall(x) (x).rbegin(),(x).rend() #define fir first #define sec second #define pb push_back #define em emplace_back #define mk make_pair #define SUM(a) accumulate(all(a),0LL) #define MIN(a) *min_element(all(a)) #define MAX(a) *max_element(all(a)) template<class... T> void input(T&... a){(cin >> ... >> a);} #define INT(...) int __VA_ARGS__;input(__VA_ARGS__) #define LL(...) ll __VA_ARGS__;input(__VA_ARGS__) #define STR(...) string __VA_ARGS__;input(__VA_ARGS__) #define DBL(...) double __VA_ARGS__;input(__VA_ARGS__) void Yes(bool iSizIs=true) {if(iSizIs){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}} void No() {cout<<"No"<<endl;} template<class T> void OUT(T x) {cout << (x) << endl;} template<class T> bool chmin(T &a, T b) {if (a > b) {a = b;return true;}return false;} template<class T> bool chmax(T &a, T b) {if (a < b) {a = b;return true;}return false;} ll POW(ll a, ll n, ll mod) { if (n == 0) return 1; if (n == 1) return a % mod; ll ret = POW(a, n / 2, mod) % mod; (ret *= ret) %= mod; if (n % 2 == 1) { (ret *= a) %= mod; } return ret; } const int inf = INT_MAX / 2; const ll infl = 1LL << 60; using vi = vector<int>; using vvi = vector<vi>; using vl = vector<ll>; using vvl = vector<vl>; using vd = vector<double>; using vvd = vector<vd>; using vs = vector<string>; using vvs = vector<vs>; using vb = vector<bool>; using vvb = vector<vb>; using pii = pair<int, int>; using pll = pair<ll, ll>; using mii = map<int, int>; using mll = map<ll, ll>; #include <atcoder/all> using namespace atcoder; #line 2 "sol.cpp" int main() { INT(n, q); dsu uni(n); set<int> s; rep(i, n) s.insert(i); rep(qi, q) { int t; cin >> t; if(t == 1) { INT(u, v); u--, v--; s.erase(uni.leader(u)); s.erase(uni.leader(v)); uni.merge(u, v); s.insert(uni.leader(u)); } else { INT(v); v--; if(s.size() == 1) { cout << -1 << endl; } else { for(auto x : s) { if(!uni.same(x, v)) { cout << x + 1 << endl; break; } } } } } }