Submission #2966023


Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

template<class VAL> struct RMQ {
    vector<pair<VAL, int> > dat;
    int SIZE_R;
    VAL INF = 1<<29; // to be set
    
    RMQ(int n = 110000) { init(n); }
    void init(int n) {
        SIZE_R = 1;
        while (SIZE_R < n) SIZE_R *= 2;
        dat.resize(SIZE_R * 2 - 1);
        for (int i = 0; i < (int)dat.size(); ++i) dat[i] = make_pair(INF, -1);
    }

    inline void set(int a, VAL v) {
        int k = a + SIZE_R - 1;
        dat[k] = make_pair(v, a);
        while (k > 0) {
            k = (k-1)/2;
            dat[k] = min(dat[k*2+1], dat[k*2+2]);
        }
    }
    
    inline pair<VAL,int> get(int a, int b, int k, int l, int r) {
        if (r <= a || b <= l) return make_pair(INF, -1);
        if (a <= l && r <= b) return dat[k];
        else {
            pair<VAL,int> vl = get(a, b, k*2+1, l, (l+r)/2);
            pair<VAL,int> vr = get(a, b, k*2+2, (l+r)/2, r);
            return min(vl, vr);
        }
    }
    inline pair<VAL,int> get(int a, int b) { return get(a, b, 0, 0, SIZE_R); }
    
    void print() {
        for (int i = 0; i < SIZE_R; ++i) {
            VAL val = (*this)[i];
            if (val < INF) cout << val;
            else cout << "INF";
            if (i != SIZE_R-1) cout << ",";
        }
        cout << endl;
    }
};

template<class Abel> struct BIT {
    vector<Abel> dat;
    Abel UNITY_SUM = 0;						// to be set
    
    /* [1, n] */
    BIT(int n = 110000) { init(n); }
    void init(int n) {
        dat.resize(n + 1);
        for (int i = 0; i < (int)dat.size(); ++i) dat[i] = UNITY_SUM;
    }
    
    /* a is 1-indexed */
    inline void add(int a, Abel x) {
        for (int i = a; i < (int)dat.size(); i += i & -i)
            dat[i] = dat[i] + x;
    }
    
    /* [1, a], a is 1-indexed */
    inline Abel sum(int a) {
        Abel res = UNITY_SUM;
        for (int i = a; i > 0; i -= i & -i)
            res = res + dat[i];
        return res;
    }
    
    /* [a, b), a and b are 1-indexed */
    inline Abel sum(int a, int b) {
        return sum(b - 1) - sum(a - 1);
    }
    
    void print() {
        for (int i = 1; i < (int)dat.size(); ++i) cout << sum(i, i + 1) << ",";
        cout << endl;
    }
};

typedef vector<vector<int> > Graph;

struct EulerTour {
    // main results
    vector<int> depth;
    vector<int> node; // the node-number of i-th element of Euler-tour
    vector<int> vf, ve; // the index of Euler-tour of node v
    
    // sub results
    RMQ<int> rmq; // depth (to find LCA)
    BIT<int> bit; // to calc sum of sub-tree
    
    EulerTour(const Graph &tree) { init(tree); }
    void init(const Graph &tree) {
        int V = (int)tree.size();
        depth.resize(V*2-1); node.resize(V*2-1); vf.resize(V); ve.resize(V);
        rmq.init(V*2-1); bit.init(V*2-1);
        int k = 0;
        dfs(tree, 0, -1, 0, k);
        for (int i = 0; i < V*2-1; ++i) rmq.set(i, depth[i]);
    }
    
    void dfs(const Graph &tree, int v, int par, int dep, int &ord) {
        node[ord] = v;
        depth[ord] = dep;
        vf[v] = ve[v] = ord;
        ++ord;
        for (int i = 0; i < tree[v].size(); ++i) {
            auto e = tree[v][i];
            if (e != par) {
                dfs(tree, e, v, dep+1, ord);
                node[ord] = v;
                depth[ord] = dep;
                ve[v] = ord;
                ++ord;
            }
        }
    }

    int LCA(int u, int v) {
        int a = vf[u], b = vf[v];
        if (a > b) swap(a, b);
        return node[rmq.get(a, b+1).second];
    }
};

/*
RMQ rmq;
BIT<int> bit;

void lca_init(int V) {
    bit.init( (V-1)*2 );
    int k = 0;
    dfs(0, -1, 0, k);
    rmq.init( V*2-1 );
    for (int i = 0; i < V*2-1; ++i) rmq.set(i, depth[i]);
    rmq.init_tree();
}

int LCA(int u, int v) {
    int a = vid[u], b = vid[v];
    if (a > b) swap(a, b);
    return cmp[ rmq.get(a, b+1).second ];
}


for (int i = 0; i < n*2; ++i) cout << cmp[i] << ", ";
cout << endl;
for (int i = 0; i < n*2; ++i) cout << depth[i] << ", ";
cout << endl;
for (int i = 0; i < n*2; ++i) cout << vid[i] << ", ";
cout << endl;
for (int i = 0; i < n*2; ++i) cout << eid[i] << ", ";
cout << endl;

rmq.print();
bit.print();
*/

int N, Q;
Graph tree;

int main() {
    cin >> N;
    tree.clear(); tree.resize(N);
    for (int i = 0; i < N-1; ++i) {
        int a, b; cin >> a >> b; --a, --b;
        tree[a].push_back(b); tree[b].push_back(a);
    }
    EulerTour et(tree);
    cin >> Q;
    for (int q = 0; q < Q; ++q) {
        int M, K; cin >> M >> K;
        vector<int> ids(M);
        for (int i = 0; i < M; ++i) {
            int v; cin >> v; --v;
            int vf = et.vf[v];
            ids[i] = vf;
            et.bit.add(vf+1, 1);
        }
        sort(ids.begin(), ids.end());
        int res = 0;
        for (int i = 0; i+K-1 < M; ++i) {
            int iu = ids[i], iv = ids[i+K-1];
            int u = et.node[iu], v = et.node[iv];
            int lca = et.LCA(u, v);
            int depth = et.depth[et.vf[lca]];
            res = max(res, depth);
        }
        cout << res << endl;
    }
}


















Submission Info

Submission Time
Task F - 根付き木のみさわさん
User drken
Language C++14 (GCC 5.4.1)
Score 130
Code Size 5358 Byte
Status AC
Exec Time 384 ms
Memory 17356 KB

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 20 / 20 110 / 110
Status
AC × 3
AC × 29
AC × 55
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
Subtask1 sample_01.txt, sample_02.txt, sample_03.txt, subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_01_18.txt, subtask_01_19.txt, subtask_01_20.txt, subtask_01_21.txt, subtask_01_22.txt, subtask_01_23.txt, subtask_01_24.txt, subtask_01_25.txt, subtask_01_26.txt
Subtask2 sample_01.txt, sample_02.txt, sample_03.txt, subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_01_18.txt, subtask_01_19.txt, subtask_01_20.txt, subtask_01_21.txt, subtask_01_22.txt, subtask_01_23.txt, subtask_01_24.txt, subtask_01_25.txt, subtask_01_26.txt, subtask_02_01.txt, subtask_02_02.txt, subtask_02_03.txt, subtask_02_04.txt, subtask_02_05.txt, subtask_02_06.txt, subtask_02_07.txt, subtask_02_08.txt, subtask_02_09.txt, subtask_02_10.txt, subtask_02_11.txt, subtask_02_12.txt, subtask_02_13.txt, subtask_02_14.txt, subtask_02_15.txt, subtask_02_16.txt, subtask_02_17.txt, subtask_02_18.txt, subtask_02_19.txt, subtask_02_20.txt, subtask_02_21.txt, subtask_02_22.txt, subtask_02_23.txt, subtask_02_24.txt, subtask_02_25.txt, subtask_02_26.txt
Case Name Status Exec Time Memory
sample_01.txt AC 3 ms 2688 KB
sample_02.txt AC 3 ms 2688 KB
sample_03.txt AC 3 ms 2688 KB
subtask_01_01.txt AC 3 ms 2688 KB
subtask_01_02.txt AC 3 ms 2688 KB
subtask_01_03.txt AC 3 ms 2688 KB
subtask_01_04.txt AC 4 ms 2688 KB
subtask_01_05.txt AC 36 ms 2688 KB
subtask_01_06.txt AC 3 ms 2688 KB
subtask_01_07.txt AC 4 ms 2688 KB
subtask_01_08.txt AC 35 ms 2816 KB
subtask_01_09.txt AC 3 ms 2688 KB
subtask_01_10.txt AC 4 ms 2688 KB
subtask_01_11.txt AC 33 ms 2816 KB
subtask_01_12.txt AC 3 ms 2688 KB
subtask_01_13.txt AC 4 ms 2688 KB
subtask_01_14.txt AC 34 ms 2816 KB
subtask_01_15.txt AC 3 ms 2688 KB
subtask_01_16.txt AC 4 ms 2688 KB
subtask_01_17.txt AC 35 ms 2816 KB
subtask_01_18.txt AC 3 ms 2688 KB
subtask_01_19.txt AC 4 ms 2688 KB
subtask_01_20.txt AC 34 ms 2816 KB
subtask_01_21.txt AC 3 ms 2688 KB
subtask_01_22.txt AC 4 ms 2688 KB
subtask_01_23.txt AC 35 ms 2816 KB
subtask_01_24.txt AC 3 ms 2688 KB
subtask_01_25.txt AC 4 ms 2688 KB
subtask_01_26.txt AC 34 ms 2816 KB
subtask_02_01.txt AC 133 ms 14592 KB
subtask_02_02.txt AC 143 ms 14592 KB
subtask_02_03.txt AC 166 ms 14592 KB
subtask_02_04.txt AC 147 ms 15232 KB
subtask_02_05.txt AC 146 ms 15232 KB
subtask_02_06.txt AC 167 ms 15232 KB
subtask_02_07.txt AC 144 ms 15308 KB
subtask_02_08.txt AC 144 ms 15052 KB
subtask_02_09.txt AC 168 ms 14924 KB
subtask_02_10.txt AC 132 ms 14592 KB
subtask_02_11.txt AC 143 ms 14592 KB
subtask_02_12.txt AC 171 ms 14592 KB
subtask_02_13.txt AC 147 ms 14720 KB
subtask_02_14.txt AC 151 ms 14720 KB
subtask_02_15.txt AC 173 ms 14720 KB
subtask_02_16.txt AC 151 ms 17100 KB
subtask_02_17.txt AC 146 ms 16844 KB
subtask_02_18.txt AC 174 ms 16844 KB
subtask_02_19.txt AC 134 ms 14720 KB
subtask_02_20.txt AC 158 ms 14720 KB
subtask_02_21.txt AC 177 ms 14720 KB
subtask_02_22.txt AC 157 ms 15820 KB
subtask_02_23.txt AC 155 ms 16844 KB
subtask_02_24.txt AC 178 ms 14924 KB
subtask_02_25.txt AC 369 ms 14720 KB
subtask_02_26.txt AC 384 ms 17356 KB