Submission #1106207

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106207		dzhoz0	Railway (BOI17_railway)	C++17	0 / 100	174 ms	68172 KiB

railway

/*
    ghmt the cutie :3
          UwU
*/

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

#define int long long
#define INF 1e18
#define f first
#define s second
#define pii pair<int, int>
#define vi vector<int>

const int MOD = 1'000'000'000 + 7;

void setIO(string name = "")
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
#ifdef LOCAL
    freopen("inp.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#else
    if (!name.empty())
    {
        freopen((name + ".INP").c_str(), "r", stdin);
        freopen((name + ".OUT").c_str(), "w", stdout);
    }
#endif
}

// START OF DEBUG
#define db(val) "["#val" = "<<(val)<<"] "
#define print_op(...) ostream& operator<<(ostream& out, const __VA_ARGS__& u)
// for printing std::pair
template<class U, class V> print_op(pair<U, V>) {
    return out << "(" << u.first << ", " << u.second << ")";
}
// for printing collection
template<class Con, class = decltype(begin(declval<Con>()))>
typename enable_if<!is_same<Con, string>::value, ostream&>::type
operator<<(ostream& out, const Con& con) { 
    out << "{";
    for (auto beg = con.begin(), it = beg; it != con.end(); ++it)
        out << (it == beg ? "" : ", ") << *it;
    return out << "}";
}
// for printing std::tuple
template<size_t i, class T> ostream& print_tuple_utils(ostream& out, const T& tup) {
    if constexpr(i == tuple_size<T>::value) return out << ")"; 
    else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); 
}
template<class ...U> print_op(tuple<U...>) {
    return print_tuple_utils<0, tuple<U...>>(out, u);
}
// END OF DEBUG

const int MAXN = 1e5;
int n, m, k;
vi g[MAXN + 5];
int h[MAXN + 5];
int up[MAXN + 5][20];
pii edges[MAXN + 5];
map<pii, int> mp;
int f[MAXN + 5];
void pre_dfs(int u, int par = 1) {
    up[u][0] = par;
    for(int i = 1; i < 20; i++) up[u][i] = up[up[u][i - 1]][i - 1];

    for(int v : g[u]) {
        if(v == par) continue;
        h[v] = h[u] + 1;
        pre_dfs(v, u);
    }
}

int LCA(int u, int v) {
    if(h[u] != h[v]) {
        if(h[u] < h[v]) swap(u, v);
        for(int i = 19; i >= 0; i--) {
            if(h[u] - h[v] >= (1 << i)) u = up[u][i];
        }
    }
    if(u == v) return u;

    for(int i = 19; i >= 0; i--) {
        if(up[u][i] != up[v][i]) u = up[u][i], v = up[v][i];
    }
    return up[u][0];
}

set<int> colors[MAXN + 5];
int val[MAXN + 5];
set<int> non[MAXN + 5];

void process_colors(int u, int par = -1) {

    for(int v : g[u]) {
        if(v == par) continue;
        process_colors(v, u);
        if(colors[u].size() < colors[v].size()) swap(colors[u], colors[v]);
        for(int x : colors[v]) colors[u].insert(x);
    }
    for(int x : non[u]) colors[u].erase(x);
    val[u] = colors[u].size();
}

void solve()
{
    cin >> n >> m >> k;
    for(int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
        edges[i] = {u, v};

    }
    pre_dfs(1, 1);
    // cout << h[5] << '\n';
    // cout << up[6][0] << '\n';
    // cout << LCA(6,5) << '\n';
    // cout << LCA(2, 3) << '\n';
    for(int i = 1; i < n; i++) {
        if(h[edges[i].f] < h[edges[i].s]) swap(edges[i].f, edges[i].s);
        mp[edges[i]] = i;

    }
    memset(f, 0, sizeof(f));
    for(int color = 1; color <= m; color++) {
        int s; cin >> s;
        vi v(s); for(int &i : v) cin >> i;
        for(int i = 1; i < s; i++) {
            int p = LCA(v[0], v[i]);
            colors[v[0]].insert(color);
            colors[v[i]].insert(color);
            non[p].insert(color);
            // if(color == 1) cout << p << ' ';
        }
        // if(color == 1) cout << '\n';
    }
    // for(int i = 1; i <= n; i++) {
    //     cout << db(i) << ' ' << db(colors[i]) << ' ' << db(non[i]) << '\n';
    // }  
    process_colors(1, 1);
    // for(int i = 1; i <= n; i++) cout << val[i] << ' '; cout << '\n';
    vi res;
    for(int i = 1; i <= n; i++) {
        if(val[i] >= 2) {
            // cout << i << ' ' << up[i][0] << '\n';
            res.push_back(mp[{i, up[i][0]}]);
        }
    } 

    sort(res.begin(), res.end());
    cout << res.size() << '\n';
    for(int x : res) cout << x << ' ';
    // cout << val[1] << '\n'; 
    // for(int i = 1; i <= n; i++) {
    //
    // }
}
signed main()
{
    setIO();
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
}

Compilation message (stderr)

railway.cpp: In function 'void setIO(std::string)':
railway.cpp:28:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         freopen((name + ".INP").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
railway.cpp:29:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         freopen((name + ".OUT").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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