Submission #584753

#	Time	Username	Problem	Language	Result	Execution time	Memory
584753		Huy	Railway (BOI17_railway)	C++17	100 / 100	112 ms	25800 KiB

railway

#include<bits/stdc++.h>
//#define int long long
#define pii pair<int,ll>
#define fi first
#define se second
/*#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")*/
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ldb = long double;
const ll N = (int)1e9 + 1;
const int maxN = (int)2e5 + 1;
const int mod = 1e9 + 7;
//const int mod = 998244353;
const int infty = 2e9 + 7;
const int base = (int)4e5;

void InputFile()
{
    //freopen("scrivener.inp","r",stdin);
    //freopen("scrivener.out","w",stdout);
    //freopen("test.out","r",stdin);
}

void FastInput()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
}

int n,m,k;
vector<vector<int>> adj;
int x[maxN],y[maxN];

void Read()
{
    cin >> n >> m >> k;
    adj.resize(n+1);
    for(int i = 1;i < n;i++)
    {
        cin >> x[i] >> y[i];
        adj[x[i]].push_back(i);
        adj[y[i]].push_back(i);
    }
}

int TimeDFS = 0;
int sta[maxN];
int of_edge[maxN];
int anc[25][maxN];
int depth[maxN];
int dp[maxN];

void PreDFS(int u,int p)
{
    sta[u] = ++TimeDFS;
    for(int i : adj[u])
    {
        int v = x[i] + y[i] - u;
        if(v == p) continue;
        of_edge[v] = i;
        depth[v] = depth[u] + 1;
        anc[0][v] = u;
        for(int i = 1;(1 << i) <= n;i++)
        {
            anc[i][v] = anc[i-1][anc[i-1][v]];
        }
        PreDFS(v,u);
    }
}

int LCA(int u,int v)
{
    if(depth[u] < depth[v]) swap(u,v);
    int k = (depth[u] - depth[v]);
    for(int i = log2(n);i >= 0;i--)
    {
        if(k & (1 << i))
        {
            u = anc[i][u];
            k ^= (1 << i);
        }
    }
    if(u == v) return u;
    for(int i = log2(n);i >= 0;i--)
    {
        if(anc[i][u] != anc[i][v])
        {
            u = anc[i][u];
            v = anc[i][v];
        }
    }
    return anc[0][u];
}

bool FA(int i,int j)
{
    return sta[i] < sta[j];
}

void DFS(int u,int p)
{
    for(int i : adj[u])
    {
        int v = x[i] + y[i] - u;
        if(v == p) continue;
        DFS(v,u);
        dp[u] += dp[v];
    }
}

void Solve()
{
    PreDFS(1,0);
    while(m--)
    {
        int sz;
        cin >> sz;
        vector<int> chosen;
        chosen.resize(sz);
        for(int i = 0;i < sz;i++)
        {
            cin >> chosen[i];
            dp[chosen[i]]++;
        }
        sort(chosen.begin(),chosen.end(),FA);
        for(int i = 0;i < sz;i++)
        {
            int nxt = (i + 1) % sz;
            dp[LCA(chosen[i],chosen[nxt])]--;
        }
    }
    DFS(1,0);
    vector<int> res;
    for(int i = 2;i <= n;i++)
    {
        if(dp[i] >= k)
        {
            res.push_back(of_edge[i]);
        }
    }

    //cout << of_edge[6];return;
    sort(res.begin(),res.end());
    cout << res.size() <<'\n';
    for(int i : res)
        cout << i <<' ';
}

void Debug()
{

}


int32_t main()
{
    FastInput();
    //InputFile();
    //int sub_type;
    //cin >> sub_type;
    //Sieve();
    //Prepare();
    int test;
    //cin >> test;
    test = 1;
    while(test--)
        //for(int prc = 1; prc <= test; prc++)
    {
        Read();
        Solve();
        //Debug();
    }
}

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