oj.uz

Submission #168198

# Submission time Handle Problem Language Result Execution time Memory
168198 2019-12-12T01:16:15 Z Leonardo_Paes Railway (BOI17_railway) C++17
36 / 100
 412 ms 30192 KB 
#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, bool ambos){
    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);

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

        if(v!=l) update_tree(1, 1, n, pos[l]+1, pos[v], 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;

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

            cin >> u;

            atuais.push_back(u);
        }

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

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

    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

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:178:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=1; j<atuais.size(); j++){
                      ~^~~~~~~~~~~~~~
railway.cpp:195:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<ans.size(); i++){
                  ~^~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2808 KB Output is correct
2 Incorrect 19 ms 4984 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2808 KB Output is correct
2 Incorrect 19 ms 4984 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 29916 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 232 ms 29592 KB Output is correct
4 Correct 219 ms 29176 KB Output is correct
5 Correct 260 ms 30104 KB Output is correct
6 Correct 271 ms 30160 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 26104 KB Output is correct
2 Correct 308 ms 23416 KB Output is correct
3 Correct 373 ms 23032 KB Output is correct
4 Correct 412 ms 23160 KB Output is correct
5 Correct 390 ms 23032 KB Output is correct
6 Correct 249 ms 26328 KB Output is correct
7 Correct 238 ms 26104 KB Output is correct

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 26104 KB Output is correct
2 Correct 308 ms 23416 KB Output is correct
3 Correct 373 ms 23032 KB Output is correct
4 Correct 412 ms 23160 KB Output is correct
5 Correct 390 ms 23032 KB Output is correct
6 Correct 249 ms 26328 KB Output is correct
7 Correct 238 ms 26104 KB Output is correct
8 Correct 248 ms 26216 KB Output is correct
9 Correct 245 ms 26224 KB Output is correct
10 Correct 264 ms 30192 KB Output is correct
11 Correct 260 ms 30064 KB Output is correct
12 Incorrect 207 ms 23768 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2808 KB Output is correct
2 Incorrect 19 ms 4984 KB Output isn't correct
3 Halted 0 ms 0 KB -