제출 #764510

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
764510		Shreyan_Paliwal	Railway (BOI17_railway)	C++17	0 / 100	213 ms	50116 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 (senator, num nodes)
                for (auto j : mp[i]) {
                    mp[nd][j.first] = 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]++;
    }

    // cout << "-------" << endl;
    // cout << nd << ' ' << num_completed[nd] << endl;
    // for (auto i : mp[nd])
    //     cout << i.first << ' ' << i.second << endl;

    // 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;
        edges[make_pair(b,a)] = i;
    }
    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);
        }
        sen_num[i] = x;
    }

    subsz(0, -1);

    dfs(0, -1);

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

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

railway.cpp: In function 'void dfs(int, int)':
railway.cpp:67:43: warning: comparison of integer expressions of different signedness: 'std::map<int, int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   67 |     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