Submission #1004507

#TimeUsernameProblemLanguageResultExecution timeMemory
1004507vjudge1Railway (BOI17_railway)C++17
29 / 100
151 ms60164 KiB
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 1000000000
int n, m, k, a, b, si;
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 == 1){
        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);
    for (int i = 0; i < n  - 1; i++){
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
        edg.push_back({a, b});
    }
    getpar(1, 0, 0);
    for (int i = 0; i < m; i++){
        cin>>si>>a>>b;
        int lc = lca(a, b);
        val[lc] -= 2, val[a]++, val[b]++;
    }
    dfs(1, 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<<" ";
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...