Submission #1840657


Source Code Expand

#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
#include "bits/stdc++.h" // define macro "/D__MAI"

using namespace std;
typedef long long int ll;

#define xprintf(fmt,...) fprintf(stderr,fmt,__VA_ARGS__)
#define debugv(v) {printf("L%d %s > ",__LINE__,#v);for(auto e:v){cout<<e<<" ";}cout<<endl;}
#define debuga(m,w) {printf("L%d %s > ",__LINE__,#m);for(int x=0;x<(w);x++){cout<<(m)[x]<<" ";}cout<<endl;}
#define debugaa(m,h,w) {printf("L%d %s >\n",__LINE__,#m);for(int y=0;y<(h);y++){for(int x=0;x<(w);x++){cout<<(m)[y][x]<<" ";}cout<<endl;}}
#define ALL(v) (v).begin(),(v).end()
#define repeat(cnt,l) for(auto cnt=0ll;(cnt)<(l);++(cnt))
#define iterate(cnt,b,e) for(auto cnt=(b);(cnt)!=(e);++(cnt))
#define MD 1000000007ll
#define PI 3.1415926535897932384626433832795
#define EPS 1e-12
template<typename T1, typename T2> ostream& operator <<(ostream &o, const pair<T1, T2> p) { o << "(" << p.first << ":" << p.second << ")"; return o; }
template<typename iterator> inline size_t argmin(iterator begin, iterator end) { return distance(begin, min_element(begin, end)); }
template<typename iterator> inline size_t argmax(iterator begin, iterator end) { return distance(begin, max_element(begin, end)); }
template<typename T> T& maxset(T& to, const T& val) { return to = max(to, val); }
template<typename T> T& minset(T& to, const T& val) { return to = min(to, val); }
void bye(string s, int code = 0) { cout << s << endl; exit(0); }
mt19937_64 randdev(8901016);
inline ll rand_range(ll l, ll h) {
    return uniform_int_distribution<ll>(l, h)(randdev);
}

#if defined(_WIN32) || defined(_WIN64)
#define getchar_unlocked _getchar_nolock
#define putchar_unlocked _putchar_nolock
#elif __GNUC__
#else
#define getchar_unlocked getchar
#define putchar_unlocked putchar
#endif
namespace {
#define isvisiblechar(c) (0x21<=(c)&&(c)<=0x7E)
    class MaiScanner {
    public:
        template<typename T> void input_integer(T& var) {
            var = 0; T sign = 1;
            int cc = getchar_unlocked();
            for (; cc<'0' || '9'<cc; cc = getchar_unlocked())
                if (cc == '-') sign = -1;
            for (; '0' <= cc&&cc <= '9'; cc = getchar_unlocked())
                var = (var << 3) + (var << 1) + cc - '0';
            var = var*sign;
        }
        inline int c() { return getchar_unlocked(); }
        inline MaiScanner& operator>>(int& var) { input_integer<int>(var); return *this; }
        inline MaiScanner& operator>>(long long& var) { input_integer<long long>(var); return *this; }
        inline MaiScanner& operator>>(string& var) {
            int cc = getchar_unlocked();
            for (; !isvisiblechar(cc); cc = getchar_unlocked());
            for (; isvisiblechar(cc); cc = getchar_unlocked())
                var.push_back(cc);
        }
        template<typename IT> void in(IT begin, IT end) { for (auto it = begin; it != end; ++it) *this >> *it; }
    };
    class MaiPrinter {
    public:
        template<typename T>
        void output_integer(T var) {
            if (var == 0) { putchar_unlocked('0'); return; }
            if (var < 0)
                putchar_unlocked('-'),
                var = -var;
            char stack[32]; int stack_p = 0;
            while (var)
                stack[stack_p++] = '0' + (var % 10),
                var /= 10;
            while (stack_p)
                putchar_unlocked(stack[--stack_p]);
        }
        inline MaiPrinter& operator<<(char c) { putchar_unlocked(c); return *this; }
        inline MaiPrinter& operator<<(int var) { output_integer<int>(var); return *this; }
        inline MaiPrinter& operator<<(long long var) { output_integer<long long>(var); return *this; }
        inline MaiPrinter& operator<<(char* str_p) { while (*str_p) putchar_unlocked(*(str_p++)); return *this; }
        inline MaiPrinter& operator<<(const string& str) {
            const char* p = str.c_str();
            const char* l = p + str.size();
            while (p < l) putchar_unlocked(*p++);
            return *this;
        }
        template<typename IT> void join(IT begin, IT end, char sep = '\n') { for (auto it = begin; it != end; ++it) *this << *it << sep; }
    };
}
MaiScanner scanner;
MaiPrinter printer;



class GraphE {
public:
    typedef int W_T;
    struct Edge {
        int u, v;
        W_T value;
        Edge(int from = 0, int to = 0, W_T value = 0) :u(from), v(to), value(value) {}
        inline int to(int _v) const { return _v == v ? u : v; }
    };
    size_t n;
    vector<vector<int>> vertex_to;
    vector<Edge> edges;

    GraphE(int n = 1) :n(n), vertex_to(n) { }

    void resize(size_t _n) {
        n = _n;
        vertex_to.resize(_n);
    }
    void connect(int from, int to, W_T val = 0) {
        vertex_to[(size_t)from].push_back((int)edges.size());
        vertex_to[(size_t)to].push_back((int)edges.size());
        edges.emplace_back(from, to, val);
    }
};


class Unionfind {
public:
    vector<int> data;
    Unionfind(size_t size = 1) : data(size, -1) { }
    bool connect(size_t x, size_t y) {
        x = root(x); y = root(y);
        if (x != y) {
            if (data[y] < data[x]) swap(x, y);
            data[x] += data[y]; data[y] = (int)x;
        }
        return x != y;
    }
    inline bool same(size_t x, size_t y) {
        return root(x) == root(y);
    }
    inline size_t root(size_t x) {
        return (size_t)(data[x] < 0 ? x : data[x] = root(data[x]));
    }
    inline int size(size_t x) {
        return -data[root(x)];
    }
};


ll m, n, n_q;
GraphE graph;

vector<array<int, 3>> queries;


// 辺番号idx未満まで接続したとき,queries[qid]が到達できる頂点の数

// i番目のクエリの答えはans[i]以下
vector<int> ans;
// 並行二分探索
void dfs_bsearch(int begin, int end, vector<int> indices_q, int depth = 0) {
    static Unionfind uf_data[20];
    static int uf_progress[20];
    if (begin == 0) uf_data[depth] = Unionfind(n); // initialize

    if (begin + 1 >= end) return;
    int c = (begin + end) / 2;

    Unionfind& uf = uf_data[depth];
    
    iterate(i, uf_progress[depth], c) {
        auto e = graph.edges[i];
        uf.connect(e.u, e.v);
    }
    uf_progress[depth] = c;

    vector<int> indices_q_left, indices_q_right;

    for (int idx_query : indices_q) {
        // このクエリの答えは[begin,end)外に存在することが分かっている
        if (ans[idx_query] < begin) continue;

        int a = queries[idx_query][0];
        int b = queries[idx_query][1];
        int cnt = uf.size(a);
        if (!uf.same(a, b))
            cnt += uf.size(b);

        if (queries[idx_query][2] <= cnt) {
            // idx_query番目のクエリの答えはc-1以下であることが分かった
            ans[idx_query] = c-1;
            indices_q_left.push_back(idx_query);
        }
        else {
            // idx_query番目のクエリの答えはc以上であることが分かった
            indices_q_right.push_back(idx_query);
        }
    }
    dfs_bsearch(begin, c, indices_q_left, depth + 1);
    dfs_bsearch(c, end,  indices_q_right, depth + 1);
}


int main() {
    scanner >> n >> m;
    graph.resize(n);

    repeat(i, m) {
        int a, b;
        scanner >> a >> b;
        --a; --b;
        graph.connect(a, b);
    }

    queries.reserve(n_q);
    scanner >> n_q;
    repeat(i, n_q) {
        int a, b, c;
        scanner >> a >> b >> c;
        --a; --b;
        queries.push_back({ a, b, c });
    }

    vector<int> indices_q(n_q);
    repeat(i, n_q) indices_q[i] = i;
    ans.resize(n_q, m-1);
    dfs_bsearch(0, m, indices_q);

    for (int a : ans) printer << a + 1 << '\n';


    return 0;
}

Submission Info

Submission Time
Task D - Stamp Rally
User m_buyoh
Language C++14 (GCC 5.4.1)
Score 1000
Code Size 7886 Byte
Status AC
Exec Time 165 ms
Memory 22196 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1000 / 1000
Status
AC × 1
AC × 33
Set Name Test Cases
Sample 0_00.txt
All 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 AC 2 ms 256 KB
1_00.txt AC 86 ms 17716 KB
1_01.txt AC 118 ms 18100 KB
1_02.txt AC 86 ms 17716 KB
1_03.txt AC 121 ms 20660 KB
1_04.txt AC 87 ms 17844 KB
1_05.txt AC 124 ms 19636 KB
1_06.txt AC 87 ms 17716 KB
1_07.txt AC 124 ms 18868 KB
1_08.txt AC 101 ms 17716 KB
1_09.txt AC 143 ms 18356 KB
1_10.txt AC 116 ms 17844 KB
1_11.txt AC 145 ms 18228 KB
1_12.txt AC 118 ms 17716 KB
1_13.txt AC 142 ms 18228 KB
1_14.txt AC 99 ms 18484 KB
1_15.txt AC 109 ms 18484 KB
1_16.txt AC 141 ms 22196 KB
1_17.txt AC 162 ms 18868 KB
1_18.txt AC 165 ms 18740 KB
1_19.txt AC 151 ms 22068 KB
1_20.txt AC 148 ms 18228 KB
1_21.txt AC 155 ms 20020 KB
1_22.txt AC 157 ms 18612 KB
1_23.txt AC 165 ms 18612 KB
1_24.txt AC 163 ms 17460 KB
1_25.txt AC 155 ms 18996 KB
1_26.txt AC 147 ms 18996 KB
1_27.txt AC 159 ms 18868 KB
1_28.txt AC 153 ms 19252 KB
1_29.txt AC 158 ms 17332 KB
1_30.txt AC 155 ms 18740 KB
1_31.txt AC 149 ms 18228 KB