Submission #486135


Source Code Expand

Copy
// Template {{{
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
using namespace std;
typedef long long LL;

#ifdef LOCAL
#include "contest.h"
#else
#define dump(x) 
#endif

class range {
    struct Iterator {
        int val, inc;
        int operator*() {return val;}
        bool operator!=(Iterator& rhs) {return val < rhs.val;}
        void operator++() {val += inc;}
    };
    Iterator i, n;
    public:
    range(int e) : i({0, 1}), n({e, 1}) {}
    range(int b, int e) : i({b, 1}), n({e, 1}) {}
    range(int b, int e, int inc) : i({b, inc}), n({e, inc}) {}
    Iterator& begin() {return i;}
    Iterator& end() {return n;}
};

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
inline bool valid(int x, int w) { return 0 <= x && x < w; }

void iostream_init() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.setf(ios::fixed);
    cout.precision(12);
}
//}}}
typedef vector<int> Node;
typedef vector<Node> Graph;
bool match[200000];
int ans;
int K;
Graph G;
int dfs(int u, int p, int d) {
    int sum = 0;
    sum += match[u];
    for(int v : G[u]) {
        if(v == p) continue;
        sum += dfs(v, u, d+1);
    }
    if(sum >= K) ans = max(ans, d);
    return sum;
}
int main(){
    iostream_init();
    int N;
    cin >> N;
    assert(N <= 100);
    G = Graph(N);
    REP(i, N-1) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    int Q;
    cin >> Q;
    REP(_, Q) {
        int M;
        cin >> M >> K;
        vector<int> v(M);
        REP(i, M) cin >> v[i];
        memset(match, 0, sizeof(match));
        REP(i, M) {
            v[i]--;
            match[v[i]] = true;
        }
        ans = -1;
        dfs(0, -1, 0);
        cout << ans << endl;
    }
    return 0;
}

/* vim:set foldmethod=marker: */

Submission Info

Submission Time
Task F - 根付き木のみさわさん
User ichyo
Language C++11 (GCC 4.9.2)
Score 20
Code Size 1938 Byte
Status
Exec Time 290 ms
Memory 1060 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt, sample_03.txt
Subtask1 20 / 20 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 0 / 110 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 28 ms 1056 KB
sample_02.txt 27 ms 984 KB
sample_03.txt 27 ms 928 KB
subtask_01_01.txt 27 ms 1048 KB
subtask_01_02.txt 28 ms 1048 KB
subtask_01_03.txt 27 ms 940 KB
subtask_01_04.txt 30 ms 928 KB
subtask_01_05.txt 241 ms 1048 KB
subtask_01_06.txt 27 ms 936 KB
subtask_01_07.txt 29 ms 932 KB
subtask_01_08.txt 246 ms 1060 KB
subtask_01_09.txt 27 ms 932 KB
subtask_01_10.txt 30 ms 920 KB
subtask_01_11.txt 246 ms 928 KB
subtask_01_12.txt 27 ms 928 KB
subtask_01_13.txt 29 ms 932 KB
subtask_01_14.txt 241 ms 1044 KB
subtask_01_15.txt 26 ms 932 KB
subtask_01_16.txt 29 ms 928 KB
subtask_01_17.txt 240 ms 1052 KB
subtask_01_18.txt 27 ms 936 KB
subtask_01_19.txt 28 ms 1052 KB
subtask_01_20.txt 247 ms 924 KB
subtask_01_21.txt 27 ms 932 KB
subtask_01_22.txt 29 ms 928 KB
subtask_01_23.txt 243 ms 932 KB
subtask_01_24.txt 27 ms 992 KB
subtask_01_25.txt 29 ms 924 KB
subtask_01_26.txt 246 ms 1048 KB
subtask_02_01.txt 281 ms 800 KB
subtask_02_02.txt 284 ms 920 KB
subtask_02_03.txt 282 ms 804 KB
subtask_02_04.txt 283 ms 928 KB
subtask_02_05.txt 283 ms 924 KB
subtask_02_06.txt 285 ms 792 KB
subtask_02_07.txt 283 ms 804 KB
subtask_02_08.txt 282 ms 824 KB
subtask_02_09.txt 284 ms 800 KB
subtask_02_10.txt 290 ms 924 KB
subtask_02_11.txt 289 ms 796 KB
subtask_02_12.txt 287 ms 804 KB
subtask_02_13.txt 290 ms 800 KB
subtask_02_14.txt 290 ms 920 KB
subtask_02_15.txt 286 ms 724 KB
subtask_02_16.txt 289 ms 800 KB
subtask_02_17.txt 284 ms 800 KB
subtask_02_18.txt 288 ms 924 KB
subtask_02_19.txt 289 ms 800 KB
subtask_02_20.txt 288 ms 800 KB
subtask_02_21.txt 282 ms 924 KB
subtask_02_22.txt 285 ms 804 KB
subtask_02_23.txt 284 ms 928 KB
subtask_02_24.txt 290 ms 800 KB
subtask_02_25.txt 290 ms 812 KB
subtask_02_26.txt 285 ms 808 KB