Submission #757374

#	Time	Username	Problem	Language	Result	Execution time	Memory
757374		anhduc2701	Railway (BOI17_railway)	C++17	100 / 100	168 ms	62144 KiB

railway

/*
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
*/
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define len(x) ll(x.size())
#define eb emplace_back
#define PI acos(-1.0)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define BIT(x, i) (1 & ((x) >> (i)))
#define MASK(x) (1LL << (x))
#define task "tnc"
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i <= (n); i++)
typedef long long ll;
typedef long double ld;
const ll INF = 1e18;
const int maxn = 3e5 + 5;
const int mod = 1e9 + 7;
const int mo = 998244353;
using pi = pair<ll, ll>;
using vi = vector<ll>;
using pii = pair<pair<ll, ll>, ll>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n, m, k;
vector<pair<int, int>> G[maxn];
vector<int> G1[maxn];
int id[maxn];
int tin[maxn];
int tout[maxn];
int eu[maxn];
int par[maxn];
pair<int, int> rmq[maxn][19];
int l = 0;
void dfs(int u, int pa)
{
    eu[++l] = u;
    tin[u] = l;
    for (auto v : G[u])
    {
        if (v.fi == pa)
            continue;
        par[v.fi] = v.se;
        dfs(v.fi, u);
        eu[++l] = u;
    }
    tout[u] = l;
}
void init()
{
    for (int i = 1; i <= l; i++)
    {
        rmq[i][0] = {tin[eu[i]], eu[i]};
    }
    for (int j = 1; (1 << j) <= l; j++)
    {
        for (int i = 1; i + (1 << j) - 1 <= l; i++)
        {
            rmq[i][j] = min(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
        }
    }
}
int LCA(int u, int v)
{
    if (tin[u] > tin[v])
        swap(u, v);
    int dis = 31 - __builtin_clz(tin[v] - tin[u] + 1);
    return min(rmq[tin[u]][dis], rmq[tin[v] - (1 << dis) + 1][dis]).se;
}
int cac[maxn];
void dfs1(int u)
{
    for (auto v : G1[u])
    {
        cac[v] += 1;
        cac[u] -= 1;
        dfs1(v);
    }
}
vector<int> ans;
void dfs2(int u, int pa)
{
    for (auto v : G[u])
    {
        if (v.fi == pa)
            continue;
        dfs2(v.fi, u);
        cac[u] += cac[v.fi];
    }
    if (cac[u] >= k)
    {
        ans.pb(par[u]);
    }
}
bool cmp(int u, int v)
{
    return tin[u] < tin[v];
}
signed main()
{
    cin.tie(0), cout.tie(0)->sync_with_stdio(0);
    cin >> n >> m >> k;
    for (int i = 1; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        G[a].pb({b, i});
        G[b].pb({a, i});
    }
    dfs(1, -1);
    init();
    for (int i = 1; i <= m; i++)
    {
        int k;
        cin >> k;
        vector<int> d;
        vector<int> d1;
        for (int j = 1; j <= k; j++)
        {
            int x;
            cin >> x;
            d.pb(x);
            G1[x].clear();
        }
        sort(d.begin(), d.end(), cmp);
        d1 = d;
        for (int j = 1; j < d.size(); j++)
        {
            d1.pb(LCA(d[j], d[j - 1]));
        }
        sort(d1.begin(), d1.end());
        d1.resize(distance(d1.begin(), unique(d1.begin(), d1.end())));
        sort(d1.begin(), d1.end(), cmp);
        for (auto v : d1)
        {
            //  cout << v << " ";
            G1[v].clear();
        }
        // cout << "\n";
        for (int j = 1; j < d1.size(); j++)
        {
            //     cout<<LCA(d1[j],d1[j-1])<<" "<<d1[j]<<"\n";
            G1[LCA(d1[j], d1[j - 1])].pb(d1[j]);
        }
        dfs1(d1[0]);
    }
    dfs2(1, -1);
    cout << ans.size() << "\n";
    sort(ans.begin(), ans.end());
    for (auto v : ans)
    {
        cout << v << " ";
    }
}

Compilation message (stderr)

railway.cpp: In function 'int main()':
railway.cpp:135:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |         for (int j = 1; j < d.size(); j++)
      |                         ~~^~~~~~~~~~
railway.cpp:148:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |         for (int j = 1; j < d1.size(); j++)
      |                         ~~^~~~~~~~~~~

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