Submission #1052620

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052620		turska	Railway (BOI17_railway)	C++17	100 / 100	146 ms	45440 KiB

railway

#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
template<typename T>
using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
 
using ll = long long;
 
using pii = pair<int, int>;
using pll = pair<ll, ll>;
 
// const ll M = 998244353;
const ll M = 1e9 + 7;
 
#define all(v) (v).begin(), (v).end()
#define ff first
#define ss second
 
const ll INFL = 1e18;
const int INF = 1e9;
const int maxN = 1e5+1;
 
int n, m, k;
vector<int> adj[maxN];
vector<int> q[maxN];
 
int cnt[maxN];
 
vector<int> ans;
map<pii, int> e;
 
map<int, int> dfs(int v, int p) {
    map<int, int> a;
 
    for (auto u: adj[v]) {
        if (u==p) continue;
        map<int, int> b = dfs(u, v);
 
        if (b.size()>=k) {
            ans.push_back(e[{v, u}]);
        }
 
        if (a.size() < b.size()) a.swap(b);
        for (auto [k, v]: b) {
            if (a[k]+v==cnt[k]) a.erase(k);
            else a[k] += v;
        }
    }
 
    for (auto u: q[v]) {
        a[u]++;
        if (a[u] == cnt[u]) a.erase(u);
    }
    return a;
 
 
}
 
 
void solve() {
    cin >> n >> m >> k;
 
    for (int i=0; i<n-1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        e[{u, v}] = i+1;
        e[{v, u}] = i+1;
    }
    for (int i=0; i<m; i++) {
        int s;
        cin >> s;
        cnt[i] = s;
        for (int j=0; j<s; j++) {
            int k;
            cin >> k;
            q[k].push_back(i);
        }
    }
    dfs(1, 1);
    sort(all(ans));
    cout << ans.size() << '\n';
    for (auto i: ans) cout << i << ' ';
    
}
 
int main() {
    ios_base::sync_with_stdio(0); cin.tie(NULL);
 
 
    int tc = 1;
    // cin >> tc;
    while (tc--) solve();
 
}

Compilation message (stderr)

railway.cpp: In function 'std::map<int, int> dfs(int, int)':
railway.cpp:44:21: warning: comparison of integer expressions of different signedness: 'std::map<int, int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   44 |         if (b.size()>=k) {
      |             ~~~~~~~~^~~

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