제출 #1370727

#제출 시각아이디문제언어결과실행 시간메모리
1370727thaibaotran555Railway (BOI17_railway)C++20
100 / 100
50 ms25372 KiB
///TRAN THAI BAO :3

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<int, int> pii;

#define maxN 100007

int n, m, k;
vector<int>adj[maxN];
pii eList[maxN];
int stt[maxN];
int in[maxN];
int ou[maxN];
int up[maxN][20];
int h[maxN] = {0};
int curT = 0;
int f[maxN] = {0};

void dfs(int u, int p)
{
    h[u] = h[p]+1;
    in[u] = ++curT;
    up[u][0] = p;
    int v;
    for(int i = 0; i < adj[u].size(); i++)
    {
        v = adj[u][i];
        if(v == p)
            continue;
        dfs(v, u);
    }
    ou[u] = curT;
}

bool cmp(int x, int y)
{
    return in[x] < in[y];
}

int lca(int u, int v)
{
    if(h[u] < h[v]) swap(u, v);
    int d = h[u] - h[v];
    for(int i = 0; i < 20; i++)
        if((d>>i)&1)
            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];
}

void dfsAns(int u, int p)
{
    int v;
    for(int i = 0; i < adj[u].size(); i++)
    {
        v = adj[u][i];
        if(v == p)
            continue;
        dfsAns(v, u);
        f[u] += f[v];
    }
}

void solve()
{
    cin >> n >> m >> k;
    int u, v;
    for(int i = 1; i < n; i++)
    {
        cin >> u >> v;
        eList[i] = {u, v};
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1, 1);
    for(int i = 1; i < n; i++)
    {
        if(up[eList[i].first][0] != eList[i].second)
            swap(eList[i].first, eList[i].second);
        stt[eList[i].first] = i;
    }
    for(int i = 1; i < 20; i++)
        for(int j = 1; j <= n; j++)
            up[j][i] = up[up[j][i-1]][i-1];
    for(int i = 0; i < m; i++)
    {
        int s, tmp;
        cin >> s;
        vector<int>a;
        for(int j = 0; j < s; j++)
        {
            cin >> tmp;
            a.push_back(tmp);
        }
        sort(a.begin(), a.end(), cmp);
        a.push_back(a.front());
        for(int j = 0; j < a.size()-1; j++)
        {
            f[a[j]]++;
            f[lca(a[j], a[j+1])]--;
        }
    }
    dfsAns(1, 1);
    int cnt = 0;
    vector<int>ans;
    for(int i = 1; i <= n; i++)
        if(f[i] >= k)
        {
            cnt++;
            ans.push_back(stt[i]);
        }
    sort(ans.begin(), ans.end());
    cout << cnt << "\n";
    for(int i = 0; i < cnt; i++)
        cout << ans[i] << " ";
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…