Submission #1271724

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271724		kigdew	Railway (BOI17_railway)	C++20	36 / 100	51 ms	21696 KiB

railway

#include <bits/stdc++.h>
using namespace std;

#define             ll    long long
#define            pii   pair<int,int>
template<class T> void   maximize(T& a,const T& b) {if (a < b) a = b;}
template<class T> void   minimize(T& a,const T& b) {if (a > b) a = b;}
#define             fi   first
#define             sc   second
#define     mset(c, x)   memset(c, x, sizeof(c))
#define   __11HA7_KZ2__  signed main()

int dx[8] = {0, 1, 0,-1, 1, 1,-1,-1};
int dy[8] = {1, 0,-1, 0, 1,-1,-1, 1};

const int N = 1e5;
const int INF = 1e9;
const ll LINF = 1e18;
/*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/

int n, m, k;
vector <pii> adj[N+15];
int timer, tin[N+15], tout[N+15];
int up[20][N+15], sum[N+15], edge_to_node[N+15];

void dfs1(int u, int p) {
    tin[u] = ++timer;

    up[0][u] = p;
    for (int k = 1; k <= 17; k++) {
        up[k][u] = up[k-1][up[k-1][u]];
    }

    for (auto [v, id] : adj[u]) {
        if (v != p) {
            edge_to_node[id] = v;
            dfs1(v, u);
        }
    }
    tout[u] = timer;
}

void dfs2(int u, int p) {
    for (auto [v, id] : adj[u]) {
        if (v != p) {
            dfs2(v, u);
            sum[u] += sum[v];
        }
    }
}

bool isAncestor(int u, int v) {
    return tin[u] <= tin[v] and tout[v] <= tout[u];
}

int lca(int u, int v) {
    if (isAncestor(u, v)) return u;
    if (isAncestor(v, u)) return v;
    for (int k = 17; k >= 0; k--) {
        if (!isAncestor(up[k][u], v)) {
            u = up[k][u];
        }
    }
    return up[0][u];
}

bool cmp(pii a, pii b) {
    return a.sc < b.sc;
}

 __11HA7_KZ2__
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m >> k;
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
    }

    timer = 0;
    dfs1(1, 1);

    for (int i = 1; i <= m; i++) {
        int s; cin >> s;
        vector <pii> vec;
        for (int j = 1; j <= s; j++) {
            int x; cin >> x;
            vec.push_back({x, tin[x]});
        }
        sort(vec.begin(), vec.end(), cmp);
        for (int j = 1; j < (int)vec.size(); j++) {
            int u = vec[j-1].fi, v = vec[j].fi;
            int anc = lca(u, v);
            sum[u]++; sum[v]++;
            sum[anc] -= 2;
        }
    }

    dfs2(1, 1);

    vector <int> ans;
    for (int e = 1; e < n; e++) {
        int u = edge_to_node[e];
        if (sum[u] >= k) ans.push_back(e);
    }

    cout << ans.size() << '\n';
    for (int x : ans) cout << x <<' ';
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 15
• Subtask 3: 7 / 7
• Subtask 4: 29 / 29
• Subtask 5: 0 / 16
• Subtask 6: 0 / 25