結果
| 問題 | No.2290 UnUnion Find |
| ユーザー |
 georgejsh
|
| 提出日時 | 2023-05-05 21:35:45 |
| 言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 327 ms / 2,000 ms |
| コード長 | 6,624 bytes |
| コンパイル時間 | 5,485 ms |
| コンパイル使用メモリ | 165,632 KB |
| 実行使用メモリ | 14,080 KB |
| 最終ジャッジ日時 | 2024-11-23 06:20:43 |
| 合計ジャッジ時間 | 18,002 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 46 |
ソースコード
#include <bits/stdc++.h>using namespace std;typedef long long int ll;typedef long double ld;typedef pair<ll, ll> pi;typedef pair<ld,ld> pd;typedef vector<ll> vi;typedef vector<ld> vd;typedef vector<pi> vpi;#define repab(i, a, b) for (ll i = (a); i < (b); i++)#define repabs(i, a, b,s) for (ll i = (a); i < (b); i+=(s))#define rep(i, a) for (ll i = 0; i < (a); i++)#define rrepab(i,a,b) for (ll i = (b)-1; i >= (a); i--)#define rrepabs(i,a,b,s) for (ll i = (b)-1; i >= (a); i-=(s))#define rrep(i,a) for (ll i = (a)-1; i >= 0; i--)#define iter(a, x) for (auto& a : x)#define repeat(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))#define GET5(a, b, c, d, e, ...) e#define F_ORC(...) GET5(__VA_ARGS__, repabs, repab, rep)#define F_ORRC(...) GET5(__VA_ARGS__, rrepabs, rrepab, rrep)#define FOR(...) F_ORC(__VA_ARGS__)(__VA_ARGS__)#define FORR(...) F_ORRC(__VA_ARGS__)(__VA_ARGS__)#define v(a) vector<array<ll,a>>#define minheap(a) priority_queue<array<ll,a>,vector<array<ll,a>>,greater<array<ll,a>> >#define mat(n,m) vector<vi> matrix(vi(m),n)#define rloop(n) int n;re(n);rep(i,n)#define array(n) array<ll,n>#define rea(arr,n) int n;re(n);vi arr(n);re(arr);#define mk make_pair#define pb push_back#define fi first#define se second#define lb lower_bound#define ub upper_bound#define sz(x) (int)x.size()#define beg(x) x.begin()#define en(x) x.end()#define all(x) beg(x), en(x)#define resz resizetemplate<class T> void ckmin(T &a, T b) { a = min(a, b); }template<class T> void ckmax(T &a, T b) { a = max(a, b); }namespace io {#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss);cerr<< "line: "<<__LINE__ <<" "; err(_it, args); cerr<<endl;}void err(istream_iterator<string> it) {}// TYPE ID (StackOverflow)template<class T> struct like_array : is_array<T>{};template<class T, size_t N> struct like_array<array<T,N>> : true_type{};template<class T> struct like_array<vector<T>> : true_type{};template<class T> bool is_like_array(const T& a) { return like_array<T>::value; }// INPUTtemplate<class T> void re(T& x) { cin >> x; }template<class Arg, class... Args> void re(Arg& first, Args&... rest);void re(double& x) { string t; re(t); x = stod(t); }void re(ld& x) { string t; re(t); x = stold(t); }template<class T1, class T2> void re(pair<T1,T2>& p);template<class T> void re(vector<T>& a);template<class T, size_t SZ> void re(array<T,SZ>& a);template<class Arg, class... Args> void re(Arg& first, Args&... rest) { re(first); re(rest...); }template<class T1, class T2> void re(pair<T1,T2>& p) { re(p.fi,p.se); }template<class T> void re(vector<T>& a) { rep(i,sz(a)) re(a[i]); }template<class T, size_t SZ> void re(array<T,SZ>& a) { rep(i,SZ) re(a[i]); }template<class T, size_t SZ> ostream& operator<<(ostream& os, const array<T,SZ>& a);template<class T> ostream& operator<<(ostream& os, const vector<T>& a);template<class T> ostream& operator<<(ostream& os, const set<T>& a) ;template<class T> ostream& operator<<(ostream& os, const multiset<T>& a) ;template<class T1, class T2> ostream& operator<<(ostream& os, const map<T1,T2>& a) ;// OUTPUTtemplate<class T1, class T2> ostream& operator<<(ostream& os, const pair<T1,T2>& a) {os << '{' << a.fi << ", " << a.se << '}'; return os;}template<class T> ostream& printArray(ostream& os, const T& a, int SZ) {os << '{';rep(i,SZ) {if (i) {os << ", ";if (is_like_array(a[i])) os << " ";}os << a[i];}os << '}';return os;}template<class T, size_t SZ> ostream& operator<<(ostream& os, const array<T,SZ>& a) {return printArray(os,a,SZ);}template<class T> ostream& operator<<(ostream& os, const vector<T>& a) {return printArray(os,a,sz(a));}template<class T> ostream& operator<<(ostream& os, const set<T>& a) {os << vector<T>(all(a)); return os;}template<class T> ostream& operator<<(ostream& os, const multiset<T>& a) {os << vector<T>(all(a)); return os;}template<class T1, class T2> ostream& operator<<(ostream& os, const map<T1,T2>& a) {os << vector<pair<T1,T2>>(all(a)); return os;}template<class T> void pr(const T& x) { cout << x << '\n'; }template<class Arg, class... Args> void pr(const Arg& first, const Args&... rest) {cout << first << ' '; pr(rest...);}template<typename T, typename... Args>void err(istream_iterator<string> it, T a, Args... args) {cerr << *it << " = " << a<<" " ;err(++it, args...);}template<typename T>void pa(vector<T> &a,bool psize=true){if(psize) cout<<a.size()<<"\n";iter(x,a) cout<<x<<" ";cout<<"\n";}}using namespace io;const int MOD = 1000000007;//const int MOD = 998244353;const ll INF = 1e18;const int MX = 2e5+1;#define yes cout<<"YES\n"#define no cout<<"NO\n"struct FU {std::vector<int> f, siz;FU() {}FU(int n) {init(n);}void init(int n) {f.resize(n);std::iota(f.begin(), f.end(), 0);siz.assign(n, 1);}int leader(int x) {while (x != f[x]) {x = f[x] = f[f[x]];}return x;}bool same(int x, int y) {return leader(x) == leader(y);}bool merge(int x, int y) {x = leader(x);y = leader(y);if (x == y) {return false;}siz[x] += siz[y];f[y] = x;return true;}int size(int x) {return siz[leader(x)];}};void solve(){int n,q;re(n,q);set<int> ss;rep(i,n) ss.insert(i);FU fu(n);rep(i,q){int ch;re(ch);if(ch==1){int u,v;re(u,v);u--,v--;u=fu.leader(u);v=fu.leader(v);if(u==v) continue;ss.erase(v);fu.merge(u,v);}else{int u;re(u);u--;u=fu.leader(u);ss.erase(u);if(sz(ss)==0)cout<<"-1\n";elsecout<<*ss.begin()+1<<"\n";ss.insert(u);}}}int main() {ios_base::sync_with_stdio(false);cin.tie(NULL);//rloop(t){solve();//}return 0;}