Submission #1162390

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162390		DangKhoizzzz	Railway (BOI17_railway)	C++20	36 / 100	149 ms	59640 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';
    sort(ans.begin() , ans.end());
    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: 7 / 7
• Subtask 4: 29 / 29
• Subtask 5: 0 / 16
• Subtask 6: 0 / 25