oj.uz

Submission #964635

# Submission time Handle Problem Language Result Execution time Memory
964635 2024-04-17T08:46:17 Z Alihan_8 Railway (BOI17_railway) C++17
23 / 100
 94 ms 69288 KB 
#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
#define int long long

using i64 = long long;

template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}

const int inf = 1e15;

const int N = 1e5 + 1;

int n;

struct SegTree{
    vector <int> T;

    SegTree(){
        T.resize(N, inf);
    }

    void upd(int v, int l, int r, int p, int val){
        if ( l == r ){
            T[v] = val;
            return;
        }
        int md = (l + r) >> 1;
        if ( p <= md ){
            upd(v * 2, l, md, p, val);
        } else{
            upd(v * 2 + 1, md + 1, r, p, val);
        }
        T[v] = min(T[v * 2], T[v * 2 + 1]);
    }

    void upd(int p, int val){
        upd(1, 0, n - 1, p, val);
    }

    int get(int v, int l, int r, int tl, int tr){
        if ( l > tr or r < tl ){
            return inf;
        }
        if ( tl <= l && tr >= r ){
            return T[v];
        }
        int md = (l + r) >> 1;
        return min(get(v * 2, l, md, tl, tr), get(v * 2 + 1, md + 1, r, tl, tr));
    }

    int get(int l, int r){
        return get(1, 0, n - 1, l, r);
    }
} seg;

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int m, k; cin >> n >> m >> k;
    vector <vector<ar<int,2>>> G(n);
    for ( int i = 0; i + 1 < n; i++ ){
        int u, v; cin >> u >> v;
        --u, --v;
        G[u].pb({v, i});
        G[v].pb({u, i});
    }
    vector <int> d(n), tin(n), tout(n), rev(n);
    vector <vector<int>> up(20, vector <int> (n));
    int ct = -1;
    auto dfs = [&](auto dfs, int u, int p) -> void{
        up[0][u] = p;
        for ( int i = 1; i < 20; i++ ){
            up[i][u] = up[i - 1][up[i - 1][u]];
        }
        tin[u] = ++ct;
        rev[tin[u]] = u;
        for ( auto &[v, j]: G[u] ){
            if ( v != p ){
                d[v] = d[u] + 1;
                dfs(dfs, v, u);
            }
        } tout[u] = ct;
    };
    dfs(dfs, 0, 0);
    auto lca = [&](int u, int v){
        if ( d[u] < d[v] ) swap(u, v);
        int df = d[u] - d[v];
        for ( int i = 0; i < 20; i++ ){
            if ( df >> i & 1 ){
                u = up[i][u];
            }
        }
        if ( u == v ){
            return u;
        }
        for ( int i = 19; i >= 0; i-- ){
            if ( up[i][u] != up[i][v] ){
                u = up[i][u];
                v = up[i][v];
            }
        }
        return up[0][u];
    };
    vector <int> cnt(n);
    auto rec = [&](auto rec, int u) -> void{
        seg.upd(tin[u], inf);
        while ( true ){
            int x = seg.get(tin[u], tout[u]);
            if ( x == inf ) break;
            x = rev[x];
            cnt[u]--, cnt[x]++;
            rec(rec, x);
        }
    };
    for ( int i = 0; i < m; i++ ){
        int s; cin >> s;
        vector <int> a(s);
        int p = -1;
        for ( auto &u: a ){
            cin >> u; --u;
            if ( p == -1 ){
                p = u;
            } else p = lca(u, p);
            seg.upd(tin[u], tin[u]);
        }
        sort(all(a), [&](int &u, int &v){
             return tin[u] < tin[v];
        });
        for ( int j = 1; j < s; j++ ){
            int p = lca(a[j - 1], a[j]);
            seg.upd(tin[p], tin[p]);
        }
        rec(rec, p);
    }
    vector <int> ans;
    auto dfs2 = [&](auto dfs2, int u, int p) -> void{
        for ( auto &[v, j]: G[u] ){
            if ( v != p ){
                dfs2(dfs2, v, u);
                if ( cnt[v] >= k ){
                    ans.pb(j);
                }
                cnt[u] += cnt[v];
            }
        }
    };
    dfs2(dfs2, 0, 0);
    sort(all(ans));
    cout << ans.size() << ln;
    for ( auto &u: ans ){
        cout << u + 1 << ' ';
    }

    cout << '\n';
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 5 ms 3932 KB Output is correct
3 Correct 5 ms 4016 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 6 ms 4440 KB Output is correct
7 Correct 6 ms 4152 KB Output is correct
8 Correct 5 ms 3968 KB Output is correct
9 Correct 5 ms 3932 KB Output is correct
10 Correct 1 ms 1252 KB Output is correct
11 Correct 1 ms 1112 KB Output is correct
12 Correct 1 ms 1116 KB Output is correct
13 Correct 1 ms 1116 KB Output is correct
14 Correct 1 ms 1116 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 5 ms 3932 KB Output is correct
3 Correct 5 ms 4016 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 6 ms 4440 KB Output is correct
7 Correct 6 ms 4152 KB Output is correct
8 Correct 5 ms 3968 KB Output is correct
9 Correct 5 ms 3932 KB Output is correct
10 Correct 1 ms 1252 KB Output is correct
11 Correct 1 ms 1112 KB Output is correct
12 Correct 1 ms 1116 KB Output is correct
13 Correct 1 ms 1116 KB Output is correct
14 Correct 1 ms 1116 KB Output is correct
15 Correct 55 ms 4332 KB Output is correct
16 Correct 63 ms 4432 KB Output is correct
17 Correct 58 ms 4436 KB Output is correct
18 Correct 6 ms 4444 KB Output is correct
19 Correct 6 ms 4104 KB Output is correct
20 Correct 45 ms 4464 KB Output is correct
21 Correct 65 ms 4460 KB Output is correct
22 Correct 1 ms 1116 KB Output is correct
23 Correct 5 ms 3932 KB Output is correct
24 Correct 5 ms 3932 KB Output is correct
25 Correct 1 ms 1112 KB Output is correct
26 Correct 1 ms 1112 KB Output is correct
27 Correct 9 ms 4444 KB Output is correct
28 Correct 6 ms 3928 KB Output is correct
29 Correct 5 ms 3932 KB Output is correct
30 Correct 5 ms 3932 KB Output is correct
31 Correct 1 ms 1116 KB Output is correct
32 Correct 1 ms 1116 KB Output is correct
33 Correct 1 ms 1116 KB Output is correct
34 Correct 1 ms 1116 KB Output is correct
35 Correct 1 ms 1116 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 84 ms 69288 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 94 ms 63564 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 94 ms 63564 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 5 ms 3932 KB Output is correct
3 Correct 5 ms 4016 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 6 ms 4440 KB Output is correct
7 Correct 6 ms 4152 KB Output is correct
8 Correct 5 ms 3968 KB Output is correct
9 Correct 5 ms 3932 KB Output is correct
10 Correct 1 ms 1252 KB Output is correct
11 Correct 1 ms 1112 KB Output is correct
12 Correct 1 ms 1116 KB Output is correct
13 Correct 1 ms 1116 KB Output is correct
14 Correct 1 ms 1116 KB Output is correct
15 Correct 55 ms 4332 KB Output is correct
16 Correct 63 ms 4432 KB Output is correct
17 Correct 58 ms 4436 KB Output is correct
18 Correct 6 ms 4444 KB Output is correct
19 Correct 6 ms 4104 KB Output is correct
20 Correct 45 ms 4464 KB Output is correct
21 Correct 65 ms 4460 KB Output is correct
22 Correct 1 ms 1116 KB Output is correct
23 Correct 5 ms 3932 KB Output is correct
24 Correct 5 ms 3932 KB Output is correct
25 Correct 1 ms 1112 KB Output is correct
26 Correct 1 ms 1112 KB Output is correct
27 Correct 9 ms 4444 KB Output is correct
28 Correct 6 ms 3928 KB Output is correct
29 Correct 5 ms 3932 KB Output is correct
30 Correct 5 ms 3932 KB Output is correct
31 Correct 1 ms 1116 KB Output is correct
32 Correct 1 ms 1116 KB Output is correct
33 Correct 1 ms 1116 KB Output is correct
34 Correct 1 ms 1116 KB Output is correct
35 Correct 1 ms 1116 KB Output is correct
36 Runtime error 84 ms 69288 KB Execution killed with signal 11
37 Halted 0 ms 0 KB -