Submission #828826

#	Time	Username	Problem	Language	Result	Execution time	Memory
828826		teesla	Railway (BOI17_railway)	C++14	100 / 100	170 ms	26528 KiB

railway

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;

int n,m,k;
vector<vector<ii>> adj; // viz e qual aresta
vector<vector<int>> sparse;
vector<int> tin,tout;
vector<int> node, res; // guarda a soma;

int t = 0;

void dfs(int x, int ant){
    t++;
    tin[x] = t;

    for(auto [a,b] : adj[x]){

        if(a == ant) continue;
        sparse[0][a] = x;
        dfs(a,x);
    }
    tout[x] = t;
    return;
}

void build(){

    for(int i=1; i<25; i++) for(int j = 0; j<n; j++){
        sparse[i][j] = sparse[i-1][sparse[i-1][j]];
    }
    return;
}

bool anc(int a, int b){// a é pai de b
    if(tin[a] <= tin[b] and tout[a] >= tout[b]) return true;
    return false;
}

int lca(int a,int b){

    if(anc(a,b)) return a;
    if(anc(b,a)) return b;

    for(int i=24; i>=0; i--){
        int novo = sparse[i][a];
        if(anc(novo, b)) continue;
        a = novo;
    }

    return sparse[0][a];
}


bool cmp(int a, int b){

    if(tout[a] != tout[b]) return tout[a] < tout[b];
    else return tin[a] > tin[b];
}


int dfs2(int x, int ant, int aresta){

    int sum = node[x];

    for(auto [a,b]: adj[x]){
        
        if(a == ant) continue;
        sum += dfs2(a,x,b);
    }

    if(sum >= k) res.push_back(aresta);
    return sum;
}

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n>> m >> k;
    adj.resize(n); tin.resize(n+3), tout.resize(n+3);

    node.assign(n, 0);
    sparse.assign(25, vector<int>(n,0));

    for(int i=0; i<n-1; i++){
        int a,b; cin >> a >> b; a--; b--;

        adj[a].push_back({b, i+1});
        adj[b].push_back({a,i+1});
    }

    dfs(0,0);
    build();


    for(int i=0; i<m; i++){

        int s; cin >> s;


        vector<int> v(s);

        int paiComum = -1;

        for(int j=0; j<s; j++){
             cin >> v[j];
            v[j]--;

            if(paiComum == -1) paiComum = v[j];
            else{paiComum = lca(paiComum, v[j]);}
        }

        //cout <<"lca "<< paiComum << endl;

        sort(v.begin(), v.end(),cmp);

        for(int j= 0; j< s; j++){

            if(j == 0){
                node[v[j]] += 1;
                node[paiComum] -= 1;
            }

            else{

                int ant = v[j-1];

                if(anc(v[j], ant)) continue;
                else{
                    node[v[j]] += 1;

                    int outro = lca(v[j], ant);
                    node[outro]-=1;
                   // cout << v[j] << endl;
                }
            }
        }

    }


    dfs2(0,0,0);

    sort(res.begin(), res.end());
    cout << res.size()<< endl;
    for(int i=0; i<res.size(); i++){
        
        if(i) cout <<' ';
        cout << res[i];
    }
    cout << endl;
}

Compilation message (stderr)

railway.cpp: In function 'void dfs(int, int)':
railway.cpp:17:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   17 |     for(auto [a,b] : adj[x]){
      |              ^
railway.cpp: In function 'int dfs2(int, int, int)':
railway.cpp:66:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   66 |     for(auto [a,b]: adj[x]){
      |              ^
railway.cpp: In function 'int main()':
railway.cpp:148:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |     for(int i=0; i<res.size(); i++){
      |                  ~^~~~~~~~~~~

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