提出 #18978749


ソースコード 拡げる

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;
    }
}

提出情報

提出日時
問題 H - Union Sets
ユーザ hal_goldfish
言語 C++ (GCC 9.2.1)
得点 600
コード長 4705 Byte
結果 AC
実行時間 296 ms
メモリ 11296 KB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 600 / 600
結果
AC × 3
AC × 49
セット名 テストケース
Sample sample_01.txt, sample_02.txt, sample_03.txt
All sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_2.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_3.txt, subtask_1_30.txt, subtask_1_31.txt, subtask_1_32.txt, subtask_1_33.txt, subtask_1_34.txt, subtask_1_35.txt, subtask_1_36.txt, subtask_1_37.txt, subtask_1_38.txt, subtask_1_39.txt, subtask_1_4.txt, subtask_1_40.txt, subtask_1_41.txt, subtask_1_42.txt, subtask_1_43.txt, subtask_1_44.txt, subtask_1_45.txt, subtask_1_46.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.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