Submission #168209

#TimeUsernameProblemLanguageResultExecution timeMemory
168209Leonardo_PaesRailway (BOI17_railway)C++11
100 / 100
504 ms30196 KiB
#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){
    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() << "\n";
 
    for(int i=0; i<ans.size(); i++){
        cout << ans[i] << " ";
    }
 
    cout << "\n";
 
    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:173:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0; j<atuais.size(); j++){
                      ~^~~~~~~~~~~~~~
railway.cpp:191:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<ans.size(); i++){
                  ~^~~~~~~~~~~
railway.cpp:158:13: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
         int last;
             ^~~~
#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...