ソースコード 拡げる

Copy
```#include<bits/stdc++.h>
using namespace std;

#define rep(i,n) for(int i = 0; i < n; i++)
#define Rep(i,n) for(int i = 1; i <= n; i++)
#define sz(x) int(x.size())
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define YesorNo(a) printf(a ? "Yes\n" : "No\n")
#define fin(a) { cout << a << endl; return 0; }
#define endl '\n'
#define fi first
#define se second
using ll = long long;
using ld = long double;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
template<class T> using V = vector<T>;
template<class T> using priq     = priority_queue<T>;
template<class T> using priq_inv = priority_queue<T, vector<T>, greater<T>>;
const int dx[] = {0,1,0,-1,1,1,-1,-1};
const int dy[] = {1,0,-1,0,1,-1,-1,1};
ll ceil(const ll &a, const ll &b){return ((a)+(b)-1)/b;}
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; }
struct INF { template<class T> operator T() { return numeric_limits<T>::max() / 2; } } INF;

template<class T, class U> istream& operator>>(istream &in, pair<T,U> &p) {
return in >> p.first >> p.second;
}
template<class T, class U> ostream& operator<<(ostream &out, const pair<T,U> &p) {
return out << '{' << p.first << ',' << p.second << '}';
}
template<class T, class U> pair<T,U> operator+(const pair<T,U> &l, const pair<T,U> &r) {
return make_pair(l.first+r.first, l.second+r.second);
}
template<class T, class U> pair<T,U> operator-(const pair<T,U> &l, const pair<T,U> &r) {
return make_pair(l.first-r.first, l.second-r.second);
}
template<class T, class U> pair<T,U> operator*(const pair<T,U> &l, const pair<T,U> &r) {
return make_pair(l.first*r.first, l.second*r.second);
}
template<class T, class U> pair<T,U> operator/(const pair<T,U> &l, const pair<T,U> &r) {
return make_pair(l.first/r.first, l.second/r.second);
}
template<class T, class U> pair<T,U>& operator+=(pair<T,U> &l, const pair<T,U> &r) { return l = l+r; }
template<class T, class U> pair<T,U>& operator-=(pair<T,U> &l, const pair<T,U> &r) { return l = l-r; }
template<class T, class U> pair<T,U>& operator*=(pair<T,U> &l, const pair<T,U> &r) { return l = l*r; }
template<class T, class U> pair<T,U>& operator/=(pair<T,U> &l, const pair<T,U> &r) { return l = l/r; }

template<class T>
istream& operator>>(istream &in, vector<T> &v) {
for(auto &e : v) in >> e;
return in;
}
template<class T>
ostream& operator<<(ostream &out, const vector<T> &v) {
for(const auto &e : v) out << e << ' ';
return out;
}

/*----------------------------------------------------------------------------------------------------*/

struct PartiallyPersistent_UnionFind {

private:
vector<int> per, gr, tim;
vector<vector<pair<int,int>>> siz;
int now_time = 0;

public:
PartiallyPersistent_UnionFind(int n):
per(n,-1), gr(1,n), tim(n, std::numeric_limits<int>::max()),
siz(n, vector<pair<int,int>>(1, make_pair(0,1))) {}

int find(int t, int x) {
if(tim[x] > t) return x;
else return find(t, per[x]);
}

bool unite(int x, int y) {
now_time++;
x = find(now_time, x);
y = find(now_time, y);
if(x == y) {
gr.push_back(gr.back());
return false;
}
gr.push_back(gr.back()-1);
if(-per[x] < -per[y]) swap(x,y);
per[x] += per[y];
per[y] = x; tim[y] = now_time;
siz[x].emplace_back(now_time, -per[x]);
return true;
}

int size(int t, int x) {
x = find(t,x);
return (*(std::lower_bound(siz[x].begin(), siz[x].end(), make_pair(t+1,0))-1)).second;
}

int lower_bound(int x, int y) {
if(!same(now_time, x, y)) return -1;
int l = 0, r = now_time;
while((r-l) > 1) {
int mid = (l+r) / 2;
if(same(mid, x, y)) r = mid;
else l = mid;
}
return r;
}

bool same(int t, int x, int y) { return find(t,x) == find(t,y); }
int group(int t) { return gr[min(t,now_time)]; }
int size() { return per.size(); }
int time() { return now_time; }
bool empty() { return per.empty(); }

};

int main(){
int n, m;
cin >> n >> m;
PartiallyPersistent_UnionFind uf(n);
rep(i,m) {
int a, b;
cin >> a >> b;
a--; b--;
uf.unite(a,b);
}

int q;
cin >> q;
rep(i,q) {
int a, b;
cin >> a >> b;
a--; b--;
cout << uf.lower_bound(a,b) << endl;
}
}```

#### 提出情報

提出日時 2020-12-25 16:59:55+0900 H - Union Sets hal_goldfish C++ (GCC 9.2.1) 600 4705 Byte AC 296 ms 11296 KB

#### ジャッジ結果

セット名 Sample All

 AC × 3
 AC × 49
セット名 テストケース
Sample sample_01.txt, sample_02.txt, sample_03.txt
ケース名 結果 実行時間 メモリ
sample_01.txt AC 4 ms 3580 KB
sample_02.txt AC 2 ms 3436 KB
sample_03.txt AC 2 ms 3468 KB
subtask_1_1.txt AC 2 ms 3568 KB
subtask_1_10.txt AC 34 ms 3700 KB
subtask_1_11.txt AC 148 ms 3944 KB
subtask_1_12.txt AC 13 ms 6400 KB
subtask_1_13.txt AC 9 ms 3660 KB
subtask_1_14.txt AC 3 ms 3568 KB
subtask_1_15.txt AC 62 ms 3488 KB
subtask_1_16.txt AC 12 ms 3576 KB
subtask_1_17.txt AC 23 ms 3396 KB
subtask_1_18.txt AC 3 ms 3476 KB
subtask_1_19.txt AC 15 ms 5876 KB
subtask_1_2.txt AC 2 ms 3516 KB
subtask_1_20.txt AC 3 ms 3452 KB
subtask_1_21.txt AC 22 ms 3572 KB
subtask_1_22.txt AC 8 ms 4608 KB
subtask_1_23.txt AC 191 ms 9412 KB
subtask_1_24.txt AC 190 ms 9332 KB
subtask_1_25.txt AC 193 ms 9504 KB
subtask_1_26.txt AC 199 ms 9416 KB
subtask_1_27.txt AC 275 ms 11084 KB
subtask_1_28.txt AC 276 ms 11076 KB
subtask_1_29.txt AC 189 ms 9464 KB
subtask_1_3.txt AC 7 ms 3576 KB
subtask_1_30.txt AC 192 ms 9392 KB
subtask_1_31.txt AC 189 ms 9416 KB
subtask_1_32.txt AC 202 ms 9456 KB
subtask_1_33.txt AC 281 ms 11296 KB
subtask_1_34.txt AC 284 ms 11260 KB
subtask_1_35.txt AC 189 ms 9452 KB
subtask_1_36.txt AC 189 ms 9408 KB
subtask_1_37.txt AC 193 ms 9356 KB
subtask_1_38.txt AC 194 ms 9676 KB
subtask_1_39.txt AC 237 ms 10820 KB
subtask_1_4.txt AC 19 ms 7752 KB
subtask_1_40.txt AC 239 ms 10824 KB
subtask_1_41.txt AC 161 ms 3572 KB
subtask_1_42.txt AC 172 ms 3568 KB
subtask_1_43.txt AC 265 ms 8472 KB
subtask_1_44.txt AC 296 ms 11088 KB
subtask_1_45.txt AC 164 ms 3600 KB
subtask_1_46.txt AC 189 ms 9432 KB
subtask_1_5.txt AC 31 ms 3588 KB
subtask_1_6.txt AC 12 ms 6188 KB
subtask_1_7.txt AC 3 ms 3812 KB
subtask_1_8.txt AC 3 ms 4064 KB
subtask_1_9.txt AC 41 ms 3976 KB