Submission #529930

#	Time	Username	Problem	Language	Result	Execution time	Memory
529930		79brue	Railway (BOI17_railway)	C++14	100 / 100	158 ms	27184 KiB

railway

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, m, k;
vector<pair<int, int> > link[100002];
int parId[100002];
int in[100002], inCnt;
int DP[100002], par[100002];
int LCADB[100002][22], depth[100002];
vector<int> ans;

void dfs(int x, int p = -1){
    in[x] = ++inCnt;
    for(auto y: link[x]){
        if(y.first == p) continue;
        par[y.first] = x;
        LCADB[y.first][0] = x;
        depth[y.first] = depth[x] + 1;
        parId[y.first] = y.second;
        dfs(y.first, x);
    }
}

int getLCA(int x, int y){
    if(depth[y] > depth[x]) swap(x, y);
    for(int i=0; i<20; i++) if((depth[x] - depth[y]) & (1<<i)) x = LCADB[x][i];
    if(x==y) return x;
    for(int d=19; d>=0; d--) if(LCADB[x][d] != LCADB[y][d]) x = LCADB[x][d], y = LCADB[y][d];
    return par[x];
}

void dfs2(int x, int par = -1){
    for(auto y: link[x]){
        if(y.first == par) continue;
        dfs2(y.first, x);
        DP[x] += DP[y.first];
        if(DP[y.first] >= 2*k) ans.push_back(parId[y.first]);
    }
}

int main(){
    scanf("%d %d %d", &n, &m, &k);
    for(int i=1; i<n; i++){
        int x, y;
        scanf("%d %d", &x, &y);
        link[x].push_back(make_pair(y, i));
        link[y].push_back(make_pair(x, i));
    }
    dfs(1);
    for(int d=1; d<20; d++) for(int i=1; i<=n; i++) LCADB[i][d] = LCADB[LCADB[i][d-1]][d-1];

    while(m--){
        vector<int> v;
        int s;
        scanf("%d", &s);
        for(int i=0; i<s; i++){
            int x;
            scanf("%d", &x);
            v.push_back(x);
        }
        if(s==1) continue;

        sort(v.begin(), v.end(), [&](auto &x, auto &y){
            return in[x] < in[y];
        });
        v.push_back(v.front());

        for(int i=0; i<s; i++){
            DP[v[i]]++;
            DP[v[i+1]]++;
            DP[getLCA(v[i], v[i+1])]-=2;
        }
    }

    dfs2(1);
    sort(ans.begin(), ans.end());
    printf("%d\n", (int)ans.size());
    for(auto p: ans) printf("%d ", p);
}

Compilation message (stderr)

railway.cpp: In function 'int main()':
railway.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |     scanf("%d %d %d", &n, &m, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
railway.cpp:48:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~
railway.cpp:58:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |         scanf("%d", &s);
      |         ~~~~~^~~~~~~~~~
railway.cpp:61:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |             scanf("%d", &x);
      |             ~~~~~^~~~~~~~~~

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