oj.uz

Submission #1097599

# Submission time Handle Problem Language Result Execution time Memory
1097599 2024-10-07T15:47:40 Z BLOBVISGOD Railway (BOI17_railway) C++17
29 / 100
 59 ms 21128 KB 
#include "bits/stdc++.h"
using namespace std;
#define rep(i,a,b) for(int i=(a); i<(b); ++i)
#define all(x) x.begin(),x.end()
#define sz(x) int(x.size())
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;

int main(){
    cin.tie(NULL),cin.sync_with_stdio(false);
    
    int n,m,k; cin >> n >> m >> k;
    vector<vector<array<int,2>>> adj(n);
    vvi par(__lg(n)+1, vi(n));
    vi d(n), ord(n), cnt(n), vis(n), E(n);
    int cc = 0;
    auto dfs = [&](int at, int dep, auto&& dfs) -> void {
        ord[at] = cc;
        vis[at] = 1;
        d[at] = dep;
        for(auto [to,id] : adj[at]) if (!vis[to]){
            par[0][to] = at;
            E[to] = id;
            dfs(to,dep+1,dfs);
        }
    };

    rep(i,0,n-1){
        int u,v; cin >> u >> v;
        u--,v--;
        adj[u].push_back({v,i+1});
        adj[v].push_back({u,i+1});
    }

    dfs(0,0,dfs);
    rep(i,0,__lg(n)) rep(j,0,n) par[i+1][j] = par[i][par[i][j]];

    auto jmp = [&](int at, int k) -> int {
        for(int i = 0; k; ++i, k/=2)
            if(k&1) at = par[i][at];
        return at;
    };
    auto lca = [&](int u, int v) -> int {
        if (d[u] < d[v]) swap(u,v);
        u = jmp(u,d[u]-d[v]);
        if (u==v) return u;
        for(int i = __lg(n); i>=0; --i)
            if (par[i][u] != par[i][v])
                u = par[i][u], v = par[i][v];
        return par[0][u];
    };

    while (m--){
        int t; cin >> t;
        vi a(t);
        rep(i,0,t) cin >> a[i], a[i]--;
        sort(all(a),[&](int u, int v){
            return ord[u] < ord[v];
        });
        int last = a[t-1];
        for(auto cur : a){
            cnt[cur]++;
            cnt[last]++;
            cnt[lca(cur,last)]-=2;
            last = cur;
        }
    }

    fill(all(vis),0);
    auto prop = [&](int at, auto&& prop) -> void {
        vis[at] = 1;
        for(auto [to,id] : adj[at]) if (!vis[to]){
            prop(to,prop);
            cnt[at] += cnt[to];
        }
    };

    prop(0,prop);

    vi ans;
    rep(i,0,n) if (cnt[i] >= 2*k) ans.push_back(E[i]);
    cout << sz(ans) << '\n';
    for(auto c : ans) cout << c << ' ';
    cout << '\n';
}

Subtask #1
0 / 8.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 21128 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 51 ms 20372 KB Output is correct
4 Correct 59 ms 19788 KB Output is correct
5 Incorrect 48 ms 20940 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 18380 KB Output is correct
2 Correct 51 ms 17100 KB Output is correct
3 Correct 57 ms 16844 KB Output is correct
4 Correct 57 ms 16844 KB Output is correct
5 Correct 57 ms 16840 KB Output is correct
6 Correct 40 ms 18640 KB Output is correct
7 Correct 39 ms 18636 KB Output is correct

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 18380 KB Output is correct
2 Correct 51 ms 17100 KB Output is correct
3 Correct 57 ms 16844 KB Output is correct
4 Correct 57 ms 16844 KB Output is correct
5 Correct 57 ms 16840 KB Output is correct
6 Correct 40 ms 18640 KB Output is correct
7 Correct 39 ms 18636 KB Output is correct
8 Incorrect 47 ms 18612 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

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