Submission #714738

#	Time	Username	Problem	Language	Result	Execution time	Memory
714738		KING	Railway (BOI17_railway)	C++14	100 / 100	253 ms	40772 KiB

railway

#include<bits/stdc++.h>
#define NOT_STONKS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

using namespace std;
const int maxn = 1e5 + 10; //4e6 + 10; //3e5 + 10;
const int mod = 1e9 + 7; //998244353;
typedef long long ll;

int n, m, k, tmp = 0, org[maxn], ans[maxn];
map<int, int> mp[maxn], cnt[maxn];
vector< pair<int, int> > adj[maxn];

void dfs(int v, int id = -1, int par = -1) {
    for (auto [ u, x ] : adj[v]) if (u != par) {
        dfs(u, x, v);
        //ans[id] += ans[x];
    }
    for (auto [ u, x ] : adj[v]) if (u != par) {
        if (cnt[u].size() > cnt[v].size()) cnt[v].swap(cnt[u]), ans[id] = ans[x];
        for (auto [ key, value ] : cnt[u]) {
            if (cnt[v][key] == 0) ans[id]++;
            cnt[v][key] += value;
            if (cnt[v][key] == org[key]) ans[id]--;
        }
        cnt[u].clear();
    }
    for (auto [ key, value ] : mp[v]) {
        if (cnt[v][key] == 0) ans[id]++;
        cnt[v][key] += value;
        if (cnt[v][key] == org[key]) ans[id]--;
    }
    mp[v].clear();
}

int main() {
    NOT_STONKS;

    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 });
    }

    for (int i = 0; i < m; i++) {
        int s;
        cin >> s;
        org[i] = s;
        for (int j = 0; j < s; j++) {
            int x;
            cin >> x;
            mp[x][i]++;
        }
    }
    dfs(1);

    vector<int> vec;
    for (int i = 1; i < n; i++) if (ans[i] >= k)
        vec.push_back(i);

    cout << vec.size() << endl;
    for (int i : vec) cout << i << " ";
    return 0;
}

Compilation message (stderr)

railway.cpp: In function 'void dfs(int, int, int)':
railway.cpp:14:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   14 |     for (auto [ u, x ] : adj[v]) if (u != par) {
      |               ^
railway.cpp:18:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   18 |     for (auto [ u, x ] : adj[v]) if (u != par) {
      |               ^
railway.cpp:20:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   20 |         for (auto [ key, value ] : cnt[u]) {
      |                   ^
railway.cpp:27:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   27 |     for (auto [ key, value ] : mp[v]) {
      |               ^

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