Submission #859319


Source Code Expand

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

#ifdef _WIN32
#define scanfll(x) scanf("%I64d", x)
#define printfll(x) printf("%I64d", x)
#else
#define scanfll(x) scanf("%lld", x)
#define printfll(x) printf("%lld", x)
#endif
#define rep(i,n) for(long long i = 0; i < (long long)(n); i++)
#define repi(i,a,b) for(long long i = (long long)(a); i < (long long)(b); i++)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define mt make_tuple
#define mp make_pair
template<class T1, class T2> bool chmin(T1 &a, T2 b) { return b < a && (a = b, true); }
template<class T1, class T2> bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }

using ll = long long; using ld = long double; using vll = vector<ll>; using vvll = vector<vll>; using vld = vector<ld>; 
using vi = vector<int>; using vvi = vector<vi>;
vll conv(vi& v) { vll r(v.size()); rep(i, v.size()) r[i] = v[i]; return r; }
using P = pair<ll, ll>;

template <typename T, typename U> ostream &operator<<(ostream &o, const pair<T, U> &v) {  o << "(" << v.first << ", " << v.second << ")"; return o; }
template<size_t...> struct seq{}; template<size_t N, size_t... Is> struct gen_seq : gen_seq<N-1, N-1, Is...>{}; template<size_t... Is> struct gen_seq<0, Is...> : seq<Is...>{};
template<class Ch, class Tr, class Tuple, size_t... Is>
void print_tuple(basic_ostream<Ch,Tr>& os, Tuple const& t, seq<Is...>){ using s = int[]; (void)s{0, (void(os << (Is == 0? "" : ", ") << get<Is>(t)), 0)...}; }
template<class Ch, class Tr, class... Args> 
auto operator<<(basic_ostream<Ch, Tr>& os, tuple<Args...> const& t) -> basic_ostream<Ch, Tr>& { os << "("; print_tuple(os, t, gen_seq<sizeof...(Args)>()); return os << ")"; }
ostream &operator<<(ostream &o, const vvll &v) { rep(i, v.size()) { rep(j, v[i].size()) o << v[i][j] << " "; cout << endl; } return o; }
template <typename T> ostream &operator<<(ostream &o, const vector<T> &v) { o << '['; rep(i, v.size()) o << v[i] << (i != v.size()-1 ? ", " : ""); o << "]";  return o; }
template <typename T>  ostream &operator<<(ostream &o, const set<T> &m) { o << '['; for (auto it = m.begin(); it != m.end(); it++) o << *it << (next(it) != m.end() ? ", " : ""); o << "]";  return o; }
template <typename T, typename U>  ostream &operator<<(ostream &o, const map<T, U> &m) { o << '['; for (auto it = m.begin(); it != m.end(); it++) o << *it << (next(it) != m.end() ? ", " : ""); o << "]";  return o; }
template <typename T, typename U>  ostream &operator<<(ostream &o, const unordered_map<T, U> &m) { o << '['; for (auto it = m.begin(); it != m.end(); it++) o << *it; o << "]";  return o; }
void printbits(ll mask, ll n) { rep(i, n) { cout << !!(mask & (1ll << i)); } cout << endl; }
#define ldout fixed << setprecision(40) 

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
//#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
//#include<list>
#include<queue>
#include<deque>
#include<algorithm>
//#include<numeric>
#include<utility>
//#include<memory>
#include<functional>
#include<cassert>
#include<set>
#include<stack>
#include<random>
 
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, -1, 0, 1};
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;
 
struct UnionFind {
    vector<int> par;
    int n, cnt;
    UnionFind(const int& x = 0) {init(x);}
    void init(const int& x) {par.assign(cnt=n=x, -1);}
    inline int find(const int& x) {return par[x] < 0 ? x : par[x] = find(par[x]);}
    inline bool same(const int& x, const int& y) {return find(x) == find(y);}
    inline bool unite(int x, int y) {
        if ((x = find(x)) == (y = find(y))) return false;
        --cnt;
        if (par[x] > par[y]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    inline int count() const {return cnt;}
    inline int count(int x) {return -par[find(x)];}

    // 特有のクエリ
    int count(int x, int y) {
        if (same(x, y)) return count(x);
        return count(x) + count(y);
    }
};
 
// 構造は、Mが時間[0, M)
// 各クエリの状態は、Query = (x, y, z)
// 各クエリは時間[fail, pass] = [-1, M-1]を持つ(差1で収束)
//
// ある時刻tでのデータ構造を利用して、(x, y, z)での特性関数を定義
// データ構造の時刻tでの時間発展を定義
//
//
// 必要なもの
// 時刻tでの特性関数を提供する関数(t, Query)
template <class query>
class TimeDependentCharacteristicFunction {
public:
    TimeDependentCharacteristicFunction(void) {};
    virtual bool test(query& q) = 0;
    virtual void next(void) = 0;
    virtual void init(void) = 0;
};


template <class query>
class BinarySearchParallel {
public:
    ll tmax;
    TimeDependentCharacteristicFunction<query>* f;
    vector<query> qs;
    vector<ll> fail;
    vector<ll> pass;

    BinarySearchParallel(ll t, TimeDependentCharacteristicFunction<query>* tdcf) 
        : tmax(t), f(tdcf) {
    }
    void addQuery(query& q) {
        qs.push_back(q);
        fail.push_back(-1);
        pass.push_back(tmax);
    }
    void solve(void) {
        rep(stage, (ll)(log(tmax) / log(2) + 2)) {
            vector<vi> check(tmax);
            rep(i, qs.size()) {
                int m = (fail[i] + pass[i])/2; // 各クエリの中心点、この中心点の時点で判定を行う。
                check[m].push_back(i);
            }
//            cout << stage << " " << check << endl;
            f->init();
            for (int i = 0; i < tmax; i++) {
                f->next();
//                uf.unite(es[i].first, es[i].second);
                for (int j = 0; j < check[i].size(); j++) {
                    ll id = check[i][j];
                    if (f->test(qs[id])) {
                        pass[id] = i;
                    } else {
                        fail[id] = i;
                    }
                    /*
                    int id = check[i][j];
                    int cnt = uf.count(qs[id].x, qs[id].y);
                    if (cnt >= qs[id].z) {
                        qs[id].r = i;
                    } else {
                        qs[id].l = i;
                    }
                    */
                }
            }
        }
    }
};

template <class query>
class TD_UnionFind : public TimeDependentCharacteristicFunction<query> {
    public:
        vector<P> op;
        UnionFind uf;
        ll t;
        ll n;
        TD_UnionFind(ll n, vector<P> op) : op(op), n(n){
            this->init();
        }
        bool test(query& q) {
            int cnt = uf.count(q.x, q.y);
            return cnt >= q.z;
        }
        void next(void) {
            uf.unite(op[t].first, op[t].second);
            t++;
        }
        void init(void) {
            t = 0;
            uf.init(n);
        }
};

struct Query {
    int x, y, z;
};


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    vector<P> es(M);
    for (int i = 0; i < M; i++) {
        cin >> es[i].first >> es[i].second; // 辺の番号とそれがつないでいるもの
        es[i].first--; es[i].second--;
    }
    BinarySearchParallel<Query> bsp(M, new TD_UnionFind<Query>(N, es));

    int Q; cin >> Q;
    vector<Query> qs(Q);
    for (int i = 0; i < Q; i++) {
        Query q;
        cin >> q.x >> q.y >> q.z;
        q.x--; q.y--;
        bsp.addQuery(q);

        /*
        cin >> qs[i].x >> qs[i].y >> qs[i].z;
        qs[i].x--; qs[i].y--;
        */
    }

    bsp.solve();

    for (int i = 0; i < bsp.fail.size(); i++) {
//        cout << bsp.fail[i] << " " << bsp.pass[i] << endl;
        cout << bsp.pass[i]+1 << endl;
    }
    return 0;
}

Submission Info

Submission Time
Task D - Stamp Rally
User hamko
Language C++14 (GCC 5.4.1)
Score 1000
Code Size 8028 Byte
Status
Exec Time 1104 ms
Memory 12860 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 0_00.txt
All 1000 / 1000 0_00.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 1_30.txt, 1_31.txt
Case Name Status Exec Time Memory
0_00.txt 14 ms 384 KB
1_00.txt 909 ms 12860 KB
1_01.txt 918 ms 12732 KB
1_02.txt 866 ms 12860 KB
1_03.txt 903 ms 12604 KB
1_04.txt 888 ms 12860 KB
1_05.txt 921 ms 12604 KB
1_06.txt 1007 ms 12860 KB
1_07.txt 986 ms 12604 KB
1_08.txt 867 ms 12860 KB
1_09.txt 923 ms 12604 KB
1_10.txt 884 ms 12860 KB
1_11.txt 932 ms 12604 KB
1_12.txt 895 ms 12732 KB
1_13.txt 940 ms 12604 KB
1_14.txt 845 ms 12348 KB
1_15.txt 872 ms 12348 KB
1_16.txt 937 ms 12312 KB
1_17.txt 1061 ms 12348 KB
1_18.txt 1104 ms 12388 KB
1_19.txt 948 ms 12348 KB
1_20.txt 949 ms 11996 KB
1_21.txt 945 ms 12376 KB
1_22.txt 954 ms 12292 KB
1_23.txt 964 ms 12368 KB
1_24.txt 962 ms 12260 KB
1_25.txt 953 ms 12280 KB
1_26.txt 940 ms 12076 KB
1_27.txt 957 ms 12268 KB
1_28.txt 950 ms 12192 KB
1_29.txt 959 ms 12288 KB
1_30.txt 958 ms 12272 KB
1_31.txt 938 ms 11988 KB