Submission #1320435

#TimeUsernameProblemLanguageResultExecution timeMemory
1320435NgTrung2217Railway (BOI17_railway)C++20
100 / 100
83 ms25292 KiB
#include <bits/stdc++.h>
#define taskname ""
using namespace std;
using ld = long double;
using ull = unsigned long long;
using ll = long long;
using pii = pair <int, int>;
const char el = '\n';
const char sp = ' ';
const int maxN = 2e5 + 10;
const int LOG = 21;

int n, m, k, timer;
int st[maxN], en[maxN], sub[maxN], head[maxN], edge_idx[maxN];
int up[maxN][LOG];
vector <pii> adj[maxN];
int bit[maxN];

void update(int x, int v)
{
    for (; x < maxN; x += x & -x) bit[x] += v;
}

int query(int x)
{
    int res = 0;
    for (; x > 0; x -= x & -x) res += bit[x];
    return res;
}

void dfs_sz(int u, int p)
{
    sub[u] = 1;
    up[u][0] = p;
    for (int i = 1; i < LOG; ++i) up[u][i] = up[up[u][i - 1]][i - 1];
    
    for (int i = 0; i < (int)adj[u].size(); ++i)
    {
        if (adj[u][i].first == p) continue;
        dfs_sz(adj[u][i].first, u);
        sub[u] += sub[adj[u][i].first];
        if (adj[u][0].first == p || sub[adj[u][i].first] > sub[adj[u][0].first])
        {
            swap(adj[u][0], adj[u][i]);
        }
    }
}

void dfs_hld(int u, int p, int h, int weight)
{
    st[u] = ++timer;
    head[u] = h;
    edge_idx[u] = weight;
    for (int i = 0; i < (int)adj[u].size(); ++i)
    {
        int v = adj[u][i].first;
        int w = adj[u][i].second;
        if (v == p) continue;
        dfs_hld(v, u, (i == 0 ? h : v), w);
    }
    en[u] = timer;
}

bool is_anc(int u, int v)
{
    return st[u] <= st[v] && en[u] >= en[v];
}

int get_lca(int u, int v)
{
    if (is_anc(u, v)) return u;
    if (is_anc(v, u)) return v;
    for (int i = LOG - 1; i >= 0; --i)
    {
        if (up[u][i] && !is_anc(up[u][i], v)) u = up[u][i];
    }
    return up[u][0];
}

void path_upd(int u, int v, int val)
{
    while (head[u] != head[v])
    {
        update(st[head[v]], val);
        update(st[v] + 1, -val);
        v = up[head[v]][0];
    }
    update(st[u], val);
    update(st[v] + 1, -val);
}

int main ()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if (fopen(taskname ".inp", "r"))
    {
        freopen(taskname ".inp", "r", stdin);
        freopen(taskname ".out", "w", stdout);
    }

    if (!(cin >> n >> m >> k)) return 0;
    for (int i = 1; i < n; ++i)
    {
        int u, v;
        cin >> u >> v;
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
    }

    dfs_sz(1, 0);
    dfs_hld(1, 0, 1, 0);

    while (m--)
    {
        int num;
        cin >> num;
        vector <int> v(num);
        for (int &x : v) cin >> x;
        sort(v.begin(), v.end(), [&](int a, int b) { return st[a] < st[b]; });
        for (int i = 1; i < num; ++i) v.push_back(get_lca(v[i - 1], v[i]));
        sort(v.begin(), v.end(), [&](int a, int b) { return st[a] < st[b]; });
        v.erase(unique(v.begin(), v.end()), v.end());

        for (int i = 1; i < (int)v.size(); ++i)
        {
            int l = get_lca(v[i - 1], v[i]);
            int curr = v[i];
            for (int j = LOG - 1; j >= 0; --j)
            {
                if (up[curr][j] && !is_anc(up[curr][j], l)) curr = up[curr][j];
            }
            path_upd(curr, v[i], 1);
        }
    }

    vector <int> res;
    for (int i = 2; i <= n; ++i)
    {
        if (query(st[i]) >= k) res.push_back(edge_idx[i]);
    }
    sort(res.begin(), res.end());

    cout << res.size() << el;
    for (int x : res) cout << x << sp;
    cout << el;

    return 0;
}

















Compilation message (stderr)

railway.cpp: In function 'int main()':
railway.cpp:98:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |         freopen(taskname ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
railway.cpp:99:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |         freopen(taskname ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...