Submission #168206

#	Time	Username	Problem	Language	Result	Execution time	Memory
168206		Leonardo_Paes	Railway (BOI17_railway)	C++17	100 / 100	669 ms	32256 KiB

railway

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5+10;

int n, m, k;

int pai[maxn], nivel[maxn], siz[maxn], in[maxn], t;

int chain[maxn], head[maxn], pos[maxn], c, qtd;

int tree[4*maxn], lazy[4*maxn];

map<pair<int,int>,int> edges;

vector<int> grafo[maxn];

void dfs(int u, int p){
    siz[u] = 1, in[u] = ++t;

    for(int i=0; i<grafo[u].size(); i++){
        int v = grafo[u][i];

        if(v==p) continue;

        pai[v] = u, nivel[v] = nivel[u] + 1;

        dfs(v, u);

        siz[v] += siz[u];
    }
}

void flush(int node, int l, int r){
    tree[node] += lazy[node] * (r-l+1);

    if(l!=r){
        lazy[2*node] += lazy[node];
        lazy[2*node+1] += lazy[node];
    }

    lazy[node] = 0;
}

void update_tree(int node, int tl, int tr, int l, int r, int val){
    flush(node, tl, tr);

    if(tl > r or tr < l) return;

    if(tl >= l and tr <= r){
        lazy[node] += val;
        flush(node, tl, tr);
        return;
    }

    int mid = (tl + tr) >> 1;

    update_tree(2*node, tl, mid, l, r, val), update_tree(2*node+1, mid+1, tr, l, r, val);

    tree[node] = tree[2*node] + tree[2*node+1];
}

int query_tree(int node, int tl, int tr, int l, int r){
    flush(node, tl, tr);
    if(tl > r or tr < l) return 0;

    if(tl >= l and tr <= r) return tree[node];

    int mid = (tl + tr) >> 1;

    return query_tree(2*node, tl, mid, l, r) + query_tree(2*node+1, mid+1, tr, l, r);
}

void hld(int u){
    if(!head[c]) head[c] = u;

    chain[u] = c, pos[u] = ++qtd;

    int maior = -1, id = -1;

    for(int i=0; i<grafo[u].size(); i++){
        int v = grafo[u][i];
        if(v!=pai[u] and siz[v] > maior){
            maior = siz[v], id = v;
        }
    }

    if(id!=-1) hld(id);

    for(int i=0; i<grafo[u].size(); i++){
        int v = grafo[u][i];
        if(v!=pai[u] and v!=id){
            c++;
            hld(v);
        }
    }
}

int lca(int u, int v){
    while(chain[u] != chain[v]){
        if(nivel[head[chain[u]]] > nivel[head[chain[v]]]) u = pai[head[chain[u]]];
        else v = pai[head[chain[v]]];
    }

    return (nivel[u] < nivel[v] ? u : v);
}

void update(int u, int v){
    int l = lca(u, v);

    while(chain[u] != chain[l]){
        update_tree(1, 1, n, pos[head[chain[u]]], pos[u], 1);
        u = pai[head[chain[u]]];
    }

    if(u!=l) update_tree(1, 1, n, pos[l]+1, pos[u], 1);
}

int query(int u){
    //cout << query_tree(1, 1, n, pos[u], pos[u]) << endl;
    return (query_tree(1, 1, n, pos[u], pos[u]) >= k);
}

bool compara(int u, int v){
    return in[u] < in[v];
}

int main(){
    //ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

    cin >> n >> m >> k;

    int tempo = 0;

    for(int i=1; i<n; i++){
        int u, v;

        cin >> u >> v;

        grafo[u].push_back(v);
        grafo[v].push_back(u);

        edges[{u, v}] = ++tempo;
        edges[{v, u}] = tempo;
    }

    dfs(1, 0);

    hld(1);

    for(int i=1; i<=m; i++){
        int s;

        cin >> s;

        vector<int> atuais;

        int last;

        for(int j=1; j<=s; j++){
            int u;

            cin >> u;

            atuais.push_back(u);

            if(j==2) last = lca(atuais[j-1], atuais[j-2]);
            else if(j>=3) last = lca(last, atuais[j-1]);
        }

        sort(atuais.begin(), atuais.end(), compara);

        for(int j=0; j<atuais.size(); j++){
            update(atuais[j], last);
            last = atuais[j];
        }
    }

    vector<int> ans;

    for(int i=2; i<=n; i++){
        if(query(i)){
            ans.push_back(edges[{i, pai[i]}]);
        }
    }

    sort(ans.begin(), ans.end());

    cout << ans.size() << endl;

    for(int i=0; i<ans.size(); i++){
        cout << ans[i] << " ";
    }

    cout << endl;

    return 0;
}

Compilation message (stderr)

railway.cpp: In function 'void dfs(int, int)':
railway.cpp:22:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<grafo[u].size(); i++){
                  ~^~~~~~~~~~~~~~~~
railway.cpp: In function 'void hld(int)':
railway.cpp:82:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<grafo[u].size(); i++){
                  ~^~~~~~~~~~~~~~~~
railway.cpp:91:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<grafo[u].size(); i++){
                  ~^~~~~~~~~~~~~~~~
railway.cpp: In function 'int main()':
railway.cpp:174:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0; j<atuais.size(); j++){
                      ~^~~~~~~~~~~~~~
railway.cpp:192:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<ans.size(); i++){
                  ~^~~~~~~~~~~
railway.cpp:159:13: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
         int last;
             ^~~~

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