Submission #527963

#	Time	Username	Problem	Language	Result	Execution time	Memory
527963		jalsol	Railway (BOI17_railway)	C++11	100 / 100	173 ms	34168 KiB

railway

#ifdef LOCAL
#include "local_header.h"
#include "debugger.h"
#else
#include <bits/stdc++.h>
#define debug(...)
#define DB(...)
#endif // LOCAL

using namespace std;

#define Task ""

struct __Init__ {
    __Init__() {
        cin.tie(nullptr)->sync_with_stdio(false);
        if (fopen(Task".inp", "r")) {
            freopen(Task".inp", "r", stdin);
            freopen(Task".out", "w", stdout); }
    }
} __init__;

using ll = long long;

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define fi first
#define se second

#define For(i, l, r) for (int i = (l); i <= (r); ++i)
#define Ford(i, r, l) for (int i = (r); i >= (l); --i)
#define Rep(i, n) For (i, 0, (n) - 1)
#define Repd(i, n) Ford (i, (n) - 1, 0)

template<class C> int isz(const C& c) { return c.size(); }
template<class T> bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } return false; }
template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } return false; }

constexpr int eps = 1e-9;
constexpr int inf = 1e9;
constexpr ll linf = 1e18;

/// ============================================================================

constexpr int maxN = 1e5 + 5;

int n, m, k;
vector<pair<int, int>> g[maxN];
int s[maxN];

map<int, int> mp[maxN];
vector<int> ans;

void Dfs(int u, int p, int pid) {
    for (const auto& e : g[u]) {
        int v, id; tie(v, id) = e;
        if (v == p) continue;

        Dfs(v, u, id);
        if (isz(mp[u]) < isz(mp[v])) {
            mp[u].swap(mp[v]);
        }

        for (const auto& x : mp[v]) {
            mp[u][x.fi] += x.se;

            if (mp[u][x.fi] == s[x.fi]) mp[u].erase(x.fi);
        }
    }

    if (isz(mp[u]) >= k) {
        ans.push_back(pid);
    }
}

signed main() {
    cin >> n >> m >> k;

    For (i, 1, n - 1) {
        int u, v; cin >> u >> v;
        g[u].emplace_back(v, i);
        g[v].emplace_back(u, i);
    }

    For (i, 1, m) {
        cin >> s[i];

        Rep (_, s[i]) {
            int u; cin >> u;
            ++mp[u][i];
        }
    }

    ans.reserve(n);
    Dfs(1, -1, -1);

    cout << isz(ans) << '\n';
    sort(all(ans));
    for (int x : ans) cout << x << ' ';
}

/**

**/

Compilation message (stderr)

railway.cpp: In constructor '__Init__::__Init__()':
railway.cpp:18:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |             freopen(Task".inp", "r", stdin);
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
railway.cpp:19:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |             freopen(Task".out", "w", stdout); }
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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