Submission #1162339

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162339		DangKhoizzzz	Railway (BOI17_railway)	C++20	0 / 100	145 ms	58820 KiB

railway

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pii pair <int , int>
#define arr3 array <int , 3>

using namespace std;

const int INF = 1e18 + 7;
const int maxn = 1e5 + 7;

int n , m , k , jump[maxn][20] , depth[maxn];

map <pii , int> ind;
vector <int> g[maxn];
vector <int> del[maxn];
vector <int> add[maxn];
vector <int> ans;

void dfsbuild(int u , int p)
{
    for(int v: g[u])
    {
        if(v == p) continue;
        jump[v][0] = u;
        depth[v] = depth[u] + 1;
        dfsbuild(v , u);
    }
}

void build()
{
    dfsbuild(1 , 1);
    for(int j = 1; j < 20; j++)
    {
        for(int i = 1; i <= n; i++)
        {
            jump[i][j] = jump[jump[i][j-1]][j-1];
        }
    }
}

int LCA(int u , int v)
{
    if(depth[u] > depth[v]) swap(u , v);
    for(int i = 17; i >= 0; i--)
    {
        if(depth[jump[v][i]] >= depth[u])
        {
            v = jump[v][i];
        }
    }
    if(u == v) return u;
    for(int i = 17; i >= 0; i--)
    {
        if(jump[v][i] != jump[u][i])
        {
            u = jump[u][i];
            v = jump[v][i];
        }
    }
    return jump[u][0];
}

void merging(set<int> &a, set<int> &b)
{
    if (a.size() < b.size()) swap(a, b);
    a.insert(b.begin(), b.end());
}

set <int> dfs(int u , int p)
{
    set <int> res;
    for(int id: add[u]) res.insert(id);
    for(int v: g[u])
    {
        if(v == p) continue;
        set <int> cc = dfs(v , u);
        merging(res , cc);
    }
    for(int id: del[u]) res.erase(id);
    if(res.size() >= k)
    {
        ans.push_back(ind[{u , jump[u][0]}]);
    }
    return res;
}



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);
        ind[{u , v}] = i;
        ind[{v , u}] = i;
    }
    build();

    while(m--)
    {
        int s; cin >> s;
        vector <int> a(s);
        for(int i = 0; i < s; i++) cin >> a[i];
        int lca = a[0];
        for(int i = 1; i < s; i++) lca = LCA(lca , a[i]);
        del[lca].push_back(m);
        for(int i = 0; i < s; i++) {add[a[i]].push_back(m);}
    }
    dfs(1 , 1);
    cout << (int)ans.size() << '\n';
    for(int id: ans) cout << id << ' ';
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

Compilation message (stderr)

railway.cpp:10:22: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   10 | const int INF = 1e18 + 7;
      |                 ~~~~~^~~

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