제출 #1004533

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1004533		vjudge1	Railway (BOI17_railway)	C++17	36 / 100	149 ms	64764 KiB

railway

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 1000000000
int n, m, k, a, dea, b, deb, si, ro, inp;
vector<vector<int>> v, up, edg;
vector<int> p, val, de;
map<vector<int>, int> ma; 
void getpar(int x, int pa, int depth){
    p[x] = pa;
    de[x] = depth;
    if (x == ro){
        pa++;
    }
    up[x][0] = pa;
    for (int i = 1; i < 20; i++){
        up[x][i] = up[up[x][i - 1]][i - 1];
    }
    for (auto el : v[x]){
        if (el != pa){
            getpar(el, x, depth + 1);
        }
    }
}
int dist(int x, int k){
    for (int i = 19; i >= 0; i--){
        int v = k & (1<<i);
        if (v != 0){
            x = up[x][i];
        }
    }
    return x;
}
int lca(int a, int b){
    if (de[a] > de[b]){
        swap(a, b);
    }
    b = dist(b, de[b] - de[a]);
    if (a == b){
        return a;
    }
    for (int i = 19; i >= 0; i--){
        int jmpa = up[a][i];
        int jmpb = up[b][i];
        if (jmpa != jmpb){
            a = jmpa;
            b = jmpb;
        }
    }
    return up[a][0];
}
ll dfs(int x, int pa){
    int sch = 0;
    for (auto el : v[x]){
        if (el != pa){
            int res = dfs(el, x);
            if (res >= k){
                ma[{x, el}] = 1;
                ma[{el, x}] = 1;
            }
            sch += res;
        }
    }
    return sch + val[x];
}
int main(){
    cin>>n>>m>>k;
    v.resize(n + 1), p.resize(n + 1), up.assign(n + 1, vector<int>(20, 1)), de.assign(n + 1, 0), val.assign(n + 1, 0);
    vector<int> ind(n + 1, 0);
    for (int i = 0; i < n  - 1; i++){
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
        ind[a]++, ind[b]++;
        edg.push_back({a, b});
    }
    for (int i = 1; i <= n; i++){
        if (ind[i] == 1){
            ro = i;
            break;
        }
    }
    getpar(ro, 0, 0);
    for (int i = 0; i < m; i++){
        cin>>si;
        dea = INF, deb = -1;
        for (int i = 0; i < si; i++){
            cin>>inp;
            if (de[inp] < dea){
                a = inp;
                dea = de[inp];
            }
            if (de[inp] > deb){
                b = inp;
                deb = de[inp];
            }
        }
        val[a]--, val[b]++;
    }
    dfs(ro, 0);
    vector<int> ans;
    for (int i = 0; i < n - 1; i++){
        if (ma[edg[i]] == 1){
            ans.push_back(i + 1);
        }
    }
    cout<<ans.size()<<"\n";
    for (auto el : ans){
        cout<<el<<" ";
    }
}

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