Submission #764485

#	Time	Username	Problem	Language	Result	Execution time	Memory
764485		Shreyan_Paliwal	Railway (BOI17_railway)	C++17	0 / 100	191 ms	48536 KiB

railway

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

const int maxn = 100000;

int n, m, k;
vector<int> adj[maxn];
map<pair<int,int>, int> edges;

int sen_num[maxn]; // num people that senator i has
vector<int> senators[maxn]; // senators that node i is part of

map<int,int> mp[maxn];
int num_completed[maxn];

vector<int> ans;

int sz[maxn];
int subsz(int nd, int par) {
    sz[nd] = 1;
    for (auto i : adj[nd])
        if (i != par)
            sz[i] += subsz(i, nd);
    return sz[nd];
}

void dfs(int nd, int par) {
    
    // get from leaves

    int maxch = -1, maxv = -1;
    for (auto i : adj[nd])
        if (i != par) {
            dfs(i, nd);
            if (maxch == -1 || sz[i] > maxv)
                maxv = sz[i], maxch = i;
        }
    if (maxch != -1) {
        num_completed[nd] = num_completed[maxch];
        swap(mp[nd], mp[maxch]);
        
        for (auto i : adj[nd])
            if (i != par && i != maxch) {
                // process pairs
                for (auto j : mp[i]) {
                    mp[nd][j.first] += j.second;
                    if (mp[nd][j.first] == sen_num[j.first])
                        num_completed[nd]++;
                }
            
                num_completed[nd] += num_completed[i];
            }
        
    }
    for (auto j : senators[nd]) {
        mp[nd][j] = mp[nd][j] + 1;
        if (mp[nd][j] == sen_num[j])
            num_completed[nd]++;
    }

    // process current
    if (mp[nd].size() - num_completed[nd] >= k) 
        ans.push_back(edges[make_pair(nd, par)]);

}


signed main() {
    // freopen("main.in", "r", stdin);
    cin >> n >> m >> k;
    for (int i = 0; i < n-1; i++) {
        int a, b; cin >> a >> b; a--, b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
        edges[make_pair(a,b)] = i+1;
        edges[make_pair(b,a)] = i+1;
    }
    for (int i = 0; i < m; i++) {
        int x; cin >> x;
        for (int j = 0; j < x; j++) {
            int y; cin >> y; y--;
            senators[y].push_back(i);
        }
    }

    subsz(0, -1);

    dfs(0, -1);

    cout << ans.size() << endl;
    for (auto i : ans)
        cout << i << ' ';
    cout << endl;

    return 0;
}

Compilation message (stderr)

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

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