oj.uz

Submission #168193

# Submission time Handle Problem Language Result Execution time Memory
168193 2019-12-12T00:54:42 Z Leonardo_Paes Railway (BOI17_railway) C++17
36 / 100
 392 ms 31856 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){
    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]}]);
        }
    }

    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:177:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=1; 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++){
                  ~^~~~~~~~~~~

Subtask #1
0 / 8.0

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

Subtask #2
0 / 15.0

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

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 29904 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 226 ms 29548 KB Output is correct
4 Correct 210 ms 29048 KB Output is correct
5 Correct 262 ms 30164 KB Output is correct
6 Correct 271 ms 30064 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 26104 KB Output is correct
2 Correct 302 ms 23452 KB Output is correct
3 Correct 346 ms 23132 KB Output is correct
4 Correct 392 ms 23176 KB Output is correct
5 Correct 376 ms 23032 KB Output is correct
6 Correct 235 ms 26236 KB Output is correct
7 Correct 230 ms 26364 KB Output is correct

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 26104 KB Output is correct
2 Correct 302 ms 23452 KB Output is correct
3 Correct 346 ms 23132 KB Output is correct
4 Correct 392 ms 23176 KB Output is correct
5 Correct 376 ms 23032 KB Output is correct
6 Correct 235 ms 26236 KB Output is correct
7 Correct 230 ms 26364 KB Output is correct
8 Correct 245 ms 26268 KB Output is correct
9 Correct 239 ms 28032 KB Output is correct
10 Correct 255 ms 31856 KB Output is correct
11 Correct 251 ms 31724 KB Output is correct
12 Incorrect 205 ms 24924 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

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