Submission #479845

#	Time	Username	Problem	Language	Result	Execution time	Memory
479845		Karliver	Railway (BOI17_railway)	C++17	100 / 100	144 ms	27332 KiB

railway

    
#include <bits/stdc++.h>

#define FIXED_FLOAT(x)  std::fixed <<std::setprecision(20) << (x)
#define all(v) (v).begin(), (v).end()
using namespace  std;
#define forn(i,n) for (int i = 0; i < (n); ++i)
#define rforn(i, n) for(int i = (n) - 1;i >= 0;--i)
#define sz(x) (int)x.size()

using ll = long long;
int mod = (ll)1e9 + 7;
#define PI acos(-1)
typedef pair<int, int> pairs;

const int INF = 1e9 + 1;
const int N = 1e5 + 100;
const double eps = 1e-7;

template <class T> using V = vector<T>;  
template <class T> using VV = V<V<T>>;  
template<class T, size_t SZ> using AR = array<T, SZ>;
template<class T> using PR = pair<T, T>;
template <typename XPAX>
bool ckma(XPAX &x, XPAX y) {
    return (x < y ? x = y, 1 : 0);
}
template <typename XPAX>
bool ckmi(XPAX &x, XPAX y) {
    return (x > y ? x = y, 1 : 0);
}
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
int n, l;
vector<vector<pairs>> g;

int timer;
vector<int> tin, tout;
vector<vector<int>> up;
vector<int> dep;
int name[N];
void dfs(int v, int p)
{
    tin[v] = timer++;
    dep[v] = (v == p ? 0 : dep[p] + 1);
    up[v][0] = p;
    for (int i = 1; i <= l; ++i)
        up[v][i] = up[up[v][i-1]][i-1];

    for (auto [u, id] : g[v]) {
        if (u != p) {
            name[u] = id;
            dfs(u, v);
        }
    }

    tout[v] = timer - 1;
}

bool is_ancestor(int u, int v)
{
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}

int lca(int u, int v)
{
    if (is_ancestor(u, v))
        return u;
    if (is_ancestor(v, u))
        return v;
    for (int i = l; i >= 0; --i) {
        if (!is_ancestor(up[u][i], v))
            u = up[u][i];
    }
    return up[u][0];
}

void preprocess(int root) {

    tin.clear();
    tout.clear();
    tin.resize(n);
    tout.resize(n);
    dep.clear();
    dep.resize(n);
    timer = 0;
    l = ceil(log2(n));
    up.assign(n, vector<int>(l + 1));
    dfs(root, root);
}

struct FenwickTree {
    vector<int> bit;  // binary indexed tree
    int n;

    FenwickTree(int n) {
        this->n = n;
        bit.assign(n, 0);
    }

    FenwickTree(vector<int> a) : FenwickTree(a.size()) {
        for (size_t i = 0; i < a.size(); i++)
            add(i, a[i]);
    }

    int sum(int r) {
        int ret = 0;
        for (; r >= 0; r = (r & (r + 1)) - 1)
            ret += bit[r];
        return ret;
    }

    int sum(int l, int r) {
        return sum(r) - sum(l - 1);
    }

    void add(int idx, int delta) {
        for (; idx < n; idx = idx | (idx + 1))
            bit[idx] += delta;
    }
};
int ck[N];
void solve() {
    int m, k;
    cin >> n >> m >> k;


    g.resize(n);

    forn(i, n - 1) {
        int a, b;
        cin >> a >> b;
        --a;--b;
        g[a].push_back({b, i});
        g[b].push_back({a, i});
    }

    preprocess(0);
    FenwickTree F(n);
    
    
    while(m--) {
        int s, ls;
        cin >> s;

        forn(i, s) {
            cin >> ck[i];
            --ck[i];
        }

        sort(ck, ck + s, [](int a, int b) {return tin[a] < tin[b];});
        ck[s] = ck[0];
        forn(i, s) {
            ls = lca(ck[i], ck[i + 1]);
            F.add(tin[ck[i]], 1);
            F.add(tin[ck[i + 1]], 1);
            F.add(tin[ls], -2);
        }
    }
    V<int> ans;

    for(int i = 1;i < n;++i) if(F.sum(tin[i], tout[i]) >= 2 * k) ans.push_back(name[i]);

    cout << sz(ans) << '\n';
    sort(all(ans));
    for(auto c : ans) {
        cout << c + 1 << ' ';
    }


}
void test_case() {
    int t;
    cin >> t;
    forn(p, t) {

        //cout << "Case #" << p + 1 << ": ";
        solve();
    }
}
int main() {

    ios::sync_with_stdio(false);
    cin.tie(0);

    solve();

}

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