Submission #205800

#	Time	Username	Problem	Language	Result	Execution time	Memory
205800		PeppaPig	Railway (BOI17_railway)	C++14	100 / 100	166 ms	24692 KiB

railway

#include <bits/stdc++.h>

#define pii pair<int, int>
#define x first
#define y  second

using namespace std;

const int N = 1e5+5;

int n, m, k;
int in[N], out[N], pos[N], hv[N], sz[N];
vector<pii> g[N];

int dfs(int u, int p) {
    static int idx = 0;

    pii ret(0, -1);
    pos[in[u] = ++idx] = u, sz[u] = 1;
    for(pii v : g[u]) if(v.x != p) {
        int z = dfs(v.x, u);
        sz[u] += z, ret = max(ret, pii(z, v.x));
    }
    hv[u] = ret.y, out[u] = idx;
    return sz[u];
}

vector<int> vec[N], ans;
int pol_sz[N], cnt[N], cur_ans;

void add(int u, bool b) {
    for(int x : vec[u]) {
        if(b) {
            if(cnt[x] == 0) ++cur_ans;
            ++cnt[x];
            if(cnt[x] == pol_sz[x]) --cur_ans;
        } else {
            if(cnt[x] == pol_sz[x]) ++cur_ans;
            --cnt[x];
            if(cnt[x] == 0) --cur_ans;
        }
    }
}

void sack(int u, int p, bool keep, int id) {
    for(pii v : g[u]) if(v.x != p && v.x != hv[u])
        sack(v.x, u, 0, v.y);
    for(pii v : g[u]) if(v.x == hv[u])
        sack(v.x, u, 1, v.y);
    for(pii v : g[u]) if(v.x != p && v.x != hv[u])
        for(int i = in[v.x]; i <= out[v.x]; i++) 
            add(pos[i], 1);
    add(u, 1);
    if(cur_ans >= k) ans.emplace_back(id);
    if(!keep) for(int i = in[u]; i <= out[u]; i++)
        add(pos[i], 0);
}

int main() {
    scanf("%d %d %d", &n, &m, &k);
    for(int i = 1, a, b; i < n; i++) {
        scanf("%d %d", &a, &b);
        g[a].emplace_back(b, i);
        g[b].emplace_back(a, i);
    }
    dfs(1, 0);
    for(int i = 1, a; i <= m; i++) {
        scanf("%d", &a);
        pol_sz[i] = a;
        for(int j = 1, b; j <= a; j++) {
            scanf("%d", &b);
            vec[b].emplace_back(i);
        }
    }
    sack(1, 0, 1, -1);

    sort(ans.begin(), ans.end());
    printf("%d\n", ans.size());
    for(int x : ans) printf("%d ", x);
    printf("\n");

    return 0;
}

Compilation message (stderr)

railway.cpp: In function 'int main()':
railway.cpp:78:30: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
     printf("%d\n", ans.size());
                    ~~~~~~~~~~^
railway.cpp:60:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n, &m, &k);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
railway.cpp:62:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~~
railway.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a);
         ~~~~~^~~~~~~~~~
railway.cpp:71:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &b);
             ~~~~~^~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 7 / 7
• Subtask 4: 29 / 29
• Subtask 5: 16 / 16
• Subtask 6: 25 / 25