oj.uz

Submission #966145

# Submission time Handle Problem Language Result Execution time Memory
966145 2024-04-19T12:29:12 Z oblantis Railway (BOI17_railway) C++17
36 / 100
 76 ms 26576 KB 
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
//#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define pb push_back
#define ss second
#define ff first
#define vt vector
#define uid(a, b) uniform_int_distribution<int>(a, b)(mt)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 2e9;
const int mod = 1e9+7;
const int maxn = 1e5;
mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
vt<int> g[maxn];
int in[maxn], up[maxn][20], dp[maxn], cnt, p[maxn];
void dfs(int v){
    in[v] = cnt++;
    for(auto i : g[v]){
        if(i == up[v][0])continue;
        up[i][0] = v, dp[i] = dp[v] + 1;
        for(int j = 1; j < 20; j++)up[i][j] = up[up[i][j - 1]][j - 1];
        dfs(i);
    }
}
bool cmp(int x, int y){
    return in[x] < in[y];
}
void checkup(int v){
    for(auto i : g[v]){
        if(i == up[v][0])continue;
        checkup(i);
        p[v] += p[i];
    }
}
int lca(int x, int y){
    if(dp[x] > dp[y])swap(x, y);
    int k = dp[y] - dp[x], j = 0;
    while(k){
        if(k & 1){
            y = up[y][j];
        }
        k >>= 1, j++;
    }
    if(y == x)return x;
    for(int j = 19; j >= 0; j--){
        if(up[x][j] != up[y][j]){
            x = up[x][j], y = up[y][j];
        }
    }
    return up[x][0];
}
void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    int u[n - 1], v[n - 1];
    for(int i = 0; i < n - 1; i++){
        cin >> u[i] >> v[i];
        --u[i], --v[i];
        g[u[i]].pb(v[i]), g[v[i]].pb(u[i]);
    }
    dfs(0);
    for(int i = 0; i < m; i++){
        int sz;
        cin >> sz;
        int c[sz];
        for(int j = 0; j < sz; j++){
            cin >> c[j];
            --c[j];
        }
        sort(c, c + sz, cmp);
        p[c[0]]++;
        p[lca(c[0], c[1])]--;
        for(int j = 1; j < sz; j++){
            p[c[j]]++;
            p[lca(c[j], c[j - 1])]--;
        }
    }
    checkup(0);
    vt<int> ans;
    for(int i = 0; i < n - 1; i++){
        if(dp[u[i]] > dp[v[i]])swap(u[i], v[i]);
        if(p[v[i]] >= k){
            ans.pb(i + 1);
        }
    }
    cout << ans.size() << '\n';
    for(auto i : ans)cout << i << ' ';
}
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int times = 1; //cin >> times;
	for(int i = 1; i <= times; i++) {
		solve();
	}
	return 0;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3420 KB Output is correct
2 Incorrect 5 ms 4700 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3420 KB Output is correct
2 Incorrect 5 ms 4700 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 26044 KB Output is correct
2 Correct 1 ms 3420 KB Output is correct
3 Correct 59 ms 25724 KB Output is correct
4 Correct 56 ms 25172 KB Output is correct
5 Correct 56 ms 26056 KB Output is correct
6 Correct 56 ms 26576 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 21332 KB Output is correct
2 Correct 54 ms 18004 KB Output is correct
3 Correct 55 ms 17492 KB Output is correct
4 Correct 54 ms 17584 KB Output is correct
5 Correct 54 ms 17492 KB Output is correct
6 Correct 52 ms 21640 KB Output is correct
7 Correct 64 ms 21412 KB Output is correct

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 21332 KB Output is correct
2 Correct 54 ms 18004 KB Output is correct
3 Correct 55 ms 17492 KB Output is correct
4 Correct 54 ms 17584 KB Output is correct
5 Correct 54 ms 17492 KB Output is correct
6 Correct 52 ms 21640 KB Output is correct
7 Correct 64 ms 21412 KB Output is correct
8 Correct 60 ms 21588 KB Output is correct
9 Correct 72 ms 21588 KB Output is correct
10 Correct 57 ms 26316 KB Output is correct
11 Correct 76 ms 26080 KB Output is correct
12 Incorrect 43 ms 17488 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3420 KB Output is correct
2 Incorrect 5 ms 4700 KB Output isn't correct
3 Halted 0 ms 0 KB -