oj.uz

Submission #1097590

# Submission time Handle Problem Language Result Execution time Memory
1097590 2024-10-07T15:25:13 Z BLOBVISGOD Railway (BOI17_railway) C++17
36 / 100
 75 ms 25300 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;

    map<pair<int,int>,int> to_input;
    vvi adj(n);
    rep(i,0,n-1){
        int u,v; cin >> u >> v;
        u--,v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
        if (u>v) swap(u,v);
        to_input[{u,v}] = i;
    }   

    int cc = 0;
    vi d(n), vis(n), dfsord(n);
    vvi par(__lg(n)+1,vi(n));
    auto dfs = [&](int at, int dep, auto&& self) -> void {
        vis[at] = 1;
        d[at] = dep;
        for(auto to : adj[at]) if (!vis[to]){
            par[0][to] = at;
            self(to,dep+1,self);
        }
        dfsord[at] = cc++;
    };
    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];
    };

    vi cnt(n);
    auto addpath = [&](int at, int rt) -> void {
        if (d[at] <= d[rt]) return;
        cnt[at]++;
        cnt[rt]--;
    };

    rep(i,0,m){
        int t; cin >> t;
        vi a(t);
        rep(j,0,t) cin >> a[j], a[j]--;
        if (t<2) continue;
        sort(all(a),[&](int u, int v){
            return dfsord[u] < dfsord[v];
        });

        rep(l,0,t){
            int r = (l+1)%t;
            int lc = lca(a[l],a[r]);
            addpath(a[l],lc);
            addpath(a[r],lc);
        }
    }

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

    prop(0, prop);

    vi ans;

    rep(i,0,n) if (cnt[i] >= k*2) ans.push_back(i);
    cout << sz(ans) << '\n';
    for(auto c : ans) {
        int ot = par[0][c];
        if (c > ot) swap(c,ot);
        cout << to_input[{c,ot}]+1 << ' ';
    }
    cout << '\n';
}

/*

9 1 1
1 2 
1 3
2 4
2 5
2 6
3 7
6 8
6 9
6 3 2 5 6 8 9

*/

/*

9 1 1
1 2 
1 3
2 4
2 5
2 6
3 7
6 8
6 9
5 7 2 5 6 8 

*/


/*

13 2 2
1 2 
1 3
2 4
2 5
2 6
3 7
6 8
6 9
7 10
1 11
11 12
12 13
9 10 3 8 9 4 13 12 11 1
5 7 2 5 6 8 

*/

/*

10 2 2
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
5 1 3 5 7 9
5 2 4 6 8 10


*/

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 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 0 ms 348 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 74 ms 25032 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 75 ms 24400 KB Output is correct
4 Correct 69 ms 23748 KB Output is correct
5 Correct 71 ms 25032 KB Output is correct
6 Correct 72 ms 25292 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 21964 KB Output is correct
2 Correct 63 ms 20680 KB Output is correct
3 Correct 71 ms 20416 KB Output is correct
4 Correct 70 ms 20544 KB Output is correct
5 Correct 68 ms 20464 KB Output is correct
6 Correct 57 ms 22152 KB Output is correct
7 Correct 54 ms 22220 KB Output is correct

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 21964 KB Output is correct
2 Correct 63 ms 20680 KB Output is correct
3 Correct 71 ms 20416 KB Output is correct
4 Correct 70 ms 20544 KB Output is correct
5 Correct 68 ms 20464 KB Output is correct
6 Correct 57 ms 22152 KB Output is correct
7 Correct 54 ms 22220 KB Output is correct
8 Correct 66 ms 22216 KB Output is correct
9 Correct 58 ms 22472 KB Output is correct
10 Correct 64 ms 25300 KB Output is correct
11 Correct 67 ms 25268 KB Output is correct
12 Incorrect 62 ms 20940 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

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