Submission #537273

#	Time	Username	Problem	Language	Result	Execution time	Memory
537273		KiriLL1ca	Railway (BOI17_railway)	C++14	100 / 100	248 ms	33004 KiB

railway

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fr first
#define sc second
//#define endl '\n'
#define pb push_back
#define sz(x) (int)((x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pw(x) (1ll << x)

#pragma GCC optimize ("-O3")
#pragma GCC optimize ("unroll-loops")

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef long double ld;

template <typename T> inline bool umax (T &a, const T &b) { return (a < b ? a = b, 1 : 0); }
template <typename T> inline bool umin (T &a, const T &b) { return (a > b ? a = b, 1 : 0); }

template <typename T>
using oset = tree<T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

auto rng = bind(uniform_int_distribution<int>(1, 1e9), mt19937(1337));

const int N = 1e5 + 100;

vector <int> g[N];
int tin[N], tout[N], timer = 0;
int up[N][21], dp[N], pr[N];
map <pii, int> mp;

inline void dfs (int v, int p) {
    tin[v] = timer++;
    up[v][0] = p;
    pr[v] = p;
    for (int i = 1; i < 20; i++) up[v][i] = up[up[v][i - 1]][i - 1];
    for (auto u : g[v]) {
        if (u != p) dfs(u, v);
    }
    tout[v] = timer++;
}

inline bool upper (int a, int b) {
    return tin[a] <= tin[b] && tout[a] >= tout[b];
}

inline int lca (int a, int b) {
    if (upper(a, b)) return a;
    if (upper(b, a)) return b;
    for (int i = 19; ~i; i--) {
        if (!upper(up[a][i], b)) a = up[a][i];
    }
    return up[a][0];
}

bool cmp (int a, int b) { return tin[a] <= tin[b]; }

inline void dfs1 (int v, int p) {
    for (auto u : g[v]) {
        if (u != p) {
            dfs1(u, v);
            dp[v] += dp[u];
        }
    }
}

signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, m, k; cin >> n >> m >> k;
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v; u--; v--;
        g[u].pb(v); g[v].pb(u);
        mp[{u, v}] = mp[{v, u}] = i;
    }
    dfs(0, 0);
    while (m--) {
        int s; cin >> s;
        vector <int> ver (s);
        for (auto &i : ver) cin >> i, i--;
        sort(all(ver), cmp);
        ver.pb(ver[0]);
        for (int i = 1; i <= s; i++) {
            int lc = lca(ver[i - 1], ver[i]);
            dp[ver[i - 1]]++;
            dp[ver[i]]++;
            dp[lc] -= 2;
        }
    }
    dfs1(0, -1);
    vector <int> ans;
    for (int i = 0; i < n; i++) {
        if (dp[i] >= k * 2) ans.pb(mp[{i, pr[i]}]);
    }
    sort(all(ans));
    cout << sz(ans) << endl;
    for (auto i : ans) cout << i << " ";
    return 0;
}

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