oj.uz

Submission #961342

# Submission time Handle Problem Language Result Execution time Memory
961342 2024-04-11T21:40:55 Z biank Railway (BOI17_railway) C++14
36 / 100
 69 ms 22864 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
#define all(x) begin(x), end(x)
 
using ii = pair<int, int>; 

const int MAX_N = 1e5 + 9;
const int MAX_K = 18;
 
vector<ii> adj[MAX_N];
int up[MAX_K][MAX_N], d[MAX_N];
int in[MAX_N], t = 0;
int idx[MAX_N];
 
void dfs(int u, int p = 0, int h = 0) {
    in[u] = ++t, up[0][u] = p, d[u] = h;
    for (auto [v, i] : adj[u]) {
        if (v != p) {
            idx[v] = i;
            dfs(v, u, h + 1);
        }
    }
}
 
void init(int n) {
    for (int i = 0; i < MAX_K - 1; i++) {
        for (int j = 1; j <= n; j++) {
            up[i + 1][j] = up[i][up[i][j]];
        }
    }
}
 
int lca(int a, int b) {
    if (d[a] < d[b]) {
        swap(a, b);
    }
    int diff = d[a] - d[b];
    for (int i = 0; i < MAX_K; i++) {
        if (diff >> i & 1) a = up[i][a];
    }
    if (a == b) {
        return a;
    }
    for (int i = MAX_K - 1; i >= 0; i--) {
        if (up[i][a] != up[i][b]) {
            a = up[i][a];
            b = up[i][b];
        }
    }
    return up[0][a];
}
 
int ans[MAX_N], c = 0, k;
 
void dfs2(int u, int p = 0) {
    for (auto [v, i] : adj[u]) {
        if (v != p) {
            dfs2(v, u);
            ans[u] += ans[v];
        }
    }
    if (ans[u] >= k) c++;
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int n, m;
    cin >> n >> m >> k;
    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].emplace_back(b, i);
        adj[b].emplace_back(a, i);
    }
    dfs(1);
    init(n);
    for (int i = 0; i < m; i++) {
        int s;
        cin >> s;
        vector<int> a(s);
        for (int j = 0; j < s; j++) {
            cin >> a[j];
        }
        sort(all(a), [&](const int &x, const int &y) {
            return in[x] < in[y];
        });
        auto nxt = [&s](int j) {
            if (++j == s) j = 0;
            return j;
        };
        for (int j = 0; j < s; j++) {
            int x = a[j], y = a[nxt(j)];
            ans[x]++;
            ans[lca(x, y)]--;
        }
    }
    dfs2(1);
    cout << c << '\n';
    for (int i = 2; i <= n; i++) {
        if (ans[i] >= k) cout << idx[i] << ' ';
    }
   
    
    return 0;
}

Compilation message

railway.cpp: In function 'void dfs(int, int, int)':
railway.cpp:19:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   19 |     for (auto [v, i] : adj[u]) {
      |               ^
railway.cpp: In function 'void dfs2(int, int)':
railway.cpp:58:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   58 |     for (auto [v, i] : adj[u]) {
      |               ^

Subtask #1
0 / 8.0

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

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 9052 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 59 ms 22588 KB Output is correct
2 Correct 2 ms 9052 KB Output is correct
3 Correct 52 ms 22612 KB Output is correct
4 Correct 46 ms 22356 KB Output is correct
5 Correct 50 ms 22808 KB Output is correct
6 Correct 56 ms 22832 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 18736 KB Output is correct
2 Correct 44 ms 15452 KB Output is correct
3 Correct 69 ms 15116 KB Output is correct
4 Correct 47 ms 15100 KB Output is correct
5 Correct 53 ms 14952 KB Output is correct
6 Correct 43 ms 18772 KB Output is correct
7 Correct 42 ms 18768 KB Output is correct

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 18736 KB Output is correct
2 Correct 44 ms 15452 KB Output is correct
3 Correct 69 ms 15116 KB Output is correct
4 Correct 47 ms 15100 KB Output is correct
5 Correct 53 ms 14952 KB Output is correct
6 Correct 43 ms 18772 KB Output is correct
7 Correct 42 ms 18768 KB Output is correct
8 Correct 49 ms 18768 KB Output is correct
9 Correct 44 ms 18768 KB Output is correct
10 Correct 47 ms 22864 KB Output is correct
11 Correct 47 ms 22832 KB Output is correct
12 Incorrect 36 ms 15192 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

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