Submission #676023

#	Time	Username	Problem	Language	Result	Execution time	Memory
676023		Trent	Railway (BOI17_railway)	C++17	100 / 100	238 ms	41180 KiB

railway

#include "bits/stdc++.h"
#include <cstring>
#include <fstream>

using namespace std;

#define forR(i, x) for(int i = 0; i < x; ++i)
#define REP(i, a, b) for(int i = (a); i < (b); ++i)
#define open(s) freopen(((string) s + ".in").c_str(), "r", stdin); freopen(((string) s + ".out").c_str(), "w", stdout)
#define all(i) i.begin(), i.end()
#define boost() cin.sync_with_stdio(0); cin.tie()
typedef long long ll;
typedef pair<int, int> pii;

const int MN = 1e5 + 10, ME=20;
struct edge{int i, ind;};
int anc[MN][ME], dep[MN], n, k;
vector<edge> adj[MN];
vector<int> add[MN], rem[MN], needed;

void fill(int c, int p, int d){
    dep[c] = d, anc[c][0] = p;
    REP(e, 1, ME) anc[c][e] = anc[c][e-1] == -1 ? -1 : anc[anc[c][e-1]][e-1];
    for(auto [i, ind] : adj[c]) if(i != p) fill(i, c, d + 1);
}

int lca(int a, int b){
    if(dep[a] > dep[b]) swap(a, b);
    for(int e = ME - 1; e >= 0; --e) if(dep[b] - (1 << e) >= dep[a]){
        b=anc[b][e];
    }
    if(a == b) return a;
    for(int e = ME - 1; e >= 0; --e) if(anc[a][e] != anc[b][e]){
        a = anc[a][e], b=anc[b][e];
    }
    return anc[a][0];
}

void join(set<int>& a, set<int>& b){
    if(a.size() < b.size()) a.swap(b);
    a.insert(all(b));
}

set<int> dfs(int c, int p, int pInd){
    set<int> has;
    for(auto [i, ind] : adj[c]) if(i != p) {
        set<int> ret = dfs(i, c, ind);
        join(has, ret);
    }
    for(int i : add[c]) has.insert(i);
    for(int i : rem[c]) has.erase(i);
    if(has.size() >= k) needed.push_back(pInd);
    // cout << c << ' ';
    // for(int i : has) cout << i << ' ';
    // cout << '\n';
    return has;
}

signed main() {
    int n, m; cin >> n >> m >> k;
    forR(g, n - 1){
        int a, b; cin >> a >> b;
        adj[a].push_back({b, g+1}); adj[b].push_back({a, g+1});
    }
    fill(1, -1, 0);
    forR(g, m){
        int s; cin >> s;
        int lc; cin >> lc;
        add[lc].push_back(g);
        forR(h, s - 1){
            int a; cin >> a;
            add[a].push_back(g);
            lc = lca(lc, a);
        }
        rem[lc].push_back(g);
    }
    dfs(1, -1, -1);
    cout << needed.size() << '\n';
    sort(all(needed));
    forR(i, needed.size()) cout << needed[i] << " \n"[i + 1 == needed.size()];
}

Compilation message (stderr)

railway.cpp: In function 'std::set<int> dfs(int, int, int)':
railway.cpp:52:19: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   52 |     if(has.size() >= k) needed.push_back(pInd);
      |        ~~~~~~~~~~~^~~~
railway.cpp: In function 'int main()':
railway.cpp:7:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define forR(i, x) for(int i = 0; i < x; ++i)
......
   80 |     forR(i, needed.size()) cout << needed[i] << " \n"[i + 1 == needed.size()];
      |          ~~~~~~~~~~~~~~~~            
railway.cpp:80:5: note: in expansion of macro 'forR'
   80 |     forR(i, needed.size()) cout << needed[i] << " \n"[i + 1 == needed.size()];
      |     ^~~~
railway.cpp:80:61: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     forR(i, needed.size()) cout << needed[i] << " \n"[i + 1 == needed.size()];
      |                                                       ~~~~~~^~~~~~~~~~~~~~~~

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