Submission #859322


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) 

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

};
 
// 構造は、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, pass;

    BinarySearchParallel(ll t, TimeDependentCharacteristicFunction<query>* tdcf) : tmax(t), f(tdcf) { }
    void addQuery(query& q) { qs.push_back(q); }

    void solve(void) {
        fail.assign(qs.size(), -1); pass.assign(qs.size(), tmax);
        rep(stage, (ll)(log(tmax) / log(2) + 2)) {
            vector<vi> check(tmax);
            rep(i, qs.size()) 
                check[(fail[i] + pass[i]) / 2].push_back(i);
            f->init();
            rep(i, tmax) {
                f->next();
                for (int id : check[i]) if (pass[id] - fail[id] > 1) 
                    (f->test(qs[id]) ? pass : fail)[id] = i;
            }
        }
    }
};

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


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); rep(i, m) { cin >> es[i].fi >> es[i].se; es[i].fi--; es[i].se--; }

    BinarySearchParallel<Query> bsp(m, new TD_UnionFind<Query>(n, es));

    int qn; cin >> qn;
    rep(_, qn) {
        Query q; cin >> q.x >> q.y >> q.z; q.x--; q.y--;
        bsp.addQuery(q);
    }

    bsp.solve();

    for (auto x : bsp.pass)
        cout << x+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 6262 Byte
Status
Exec Time 1099 ms
Memory 11452 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 6 ms 512 KB
1_00.txt 855 ms 11452 KB
1_01.txt 1056 ms 11324 KB
1_02.txt 874 ms 11452 KB
1_03.txt 893 ms 11068 KB
1_04.txt 971 ms 11452 KB
1_05.txt 1053 ms 11196 KB
1_06.txt 913 ms 11452 KB
1_07.txt 914 ms 11196 KB
1_08.txt 1015 ms 11452 KB
1_09.txt 1073 ms 11196 KB
1_10.txt 1032 ms 11452 KB
1_11.txt 944 ms 11196 KB
1_12.txt 964 ms 11324 KB
1_13.txt 1082 ms 11196 KB
1_14.txt 893 ms 10812 KB
1_15.txt 1005 ms 10812 KB
1_16.txt 909 ms 10264 KB
1_17.txt 1004 ms 10556 KB
1_18.txt 967 ms 10468 KB
1_19.txt 921 ms 10556 KB
1_20.txt 976 ms 9948 KB
1_21.txt 940 ms 10584 KB
1_22.txt 942 ms 10244 KB
1_23.txt 949 ms 10576 KB
1_24.txt 1099 ms 10468 KB
1_25.txt 952 ms 10616 KB
1_26.txt 923 ms 10028 KB
1_27.txt 942 ms 10476 KB
1_28.txt 978 ms 10144 KB
1_29.txt 950 ms 10240 KB
1_30.txt 963 ms 10480 KB
1_31.txt 1071 ms 9940 KB