Submission #1038574

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038574		krakenn	Railway (BOI17_railway)	C++17	100 / 100	72 ms	25288 KiB

railway

#include "bits/stdc++.h"
using namespace std;

#define ll long long
#define ld long double
#define ii pair<int,int>
#define pll pair<ll,ll>
#define lll tuple<ll,ll,ll>
#define iii tuple<int,int,int>
#define forn(i,a,b) for (int i = a; i <= b; i++)
#define sz(x) int((x).size())
#define all(x) begin(x), end(x)
#define dbg(v) \
cout << "Line(" << __LINE__ << ") -> " << #v << " = " << (v) << endl;

#define m1(x) template<class T, class... U> void x(T&& a, U&&... b)
#define m2(x) (int[]){(x forward<U>(b),0)...}
m1(out) { cout << forward<T>(a);  m2(cout << " " <<); cout << "\n"; }
m1(in) { cin >> forward<T>(a); m2(cin >>); }

// nmax = 1e5

int tin[100004], tout[100004], timer = 0, p_edge[100004];
vector<ii> adj[100004];

void dfs2(int node = 1, int parent = 0) {
    tin[node] = ++timer;
    for (pair<int, int> &i : adj[node])
        if (i.first != parent) {
            p_edge[i.first] = i.second;
            dfs2(i.first, node);
        }
    tout[node] = timer;
}

template <typename T> class BinaryLift {
    public:
    int lgmax = 20;
    int nmax = 0;
    vector<vector<int>> far;
    vector<int> level;

    BinaryLift(int n): lgmax(__bit_width(n)+1), nmax(n), far(lgmax+1, vector<int>(nmax+3, 0)),
        level(nmax+3) {
        level[1] = 0;
        dfs(1, -1);

        for(int h = 1; h <= lgmax; h++) {
            for(int i = 1; i <= nmax; i++) {
                far[h][i] = far[h - 1][far[h - 1][i]];
            }
        }
    }

    int getLca(int x, int y) {
        if(level[x] < level[y]) swap(x, y);
        for(int h = lgmax; h >= 0; h--)
            if(level[y] + (1 << h) <= level[x]){
                x = far[h][x];
            }      
        if(x == y) return x;
        for(int h = lgmax; h >= 0; h--)
            if(far[h][x] != far[h][y]) {
                x = far[h][x];
                y = far[h][y];
            }
        return far[0][x];
    }

    void dfs(int now, int p) {
        for(auto &[v, cost]: adj[now]) {
            if(v != p) {
                // init
                far[0][v] = now;
                level[v] = level[now] + 1;
                dfs(v, now);
            }
        }
    }

    int kth(int node, int k){
        // beware k too high!
        int x = node;
        for(int h = lgmax; h >= 0; h--){
            if(k & (1 << h)){
                x = far[h][x];
            }
        }
        return x;
    }
};

class FenwickTree {
    private:
        vector<ll> f;
    
    public:
        int LSOne(int i){return (i&(-i));}
        FenwickTree(int n){
            f.assign(n+1, 0);
        }

        void update(int x, ll v){
            for(int i = x; i <= (int)f.size()-1; i += LSOne(i)){
                f[i] += v;
            }
        }

        void update(int l, int r, ll v){
            update(l, v);
            update(r+1, -v);
        }

        ll print(int k){
            ll sum = 0;
            for(int i = k; i >= 1; i -= LSOne(i)){
                sum += f[i];
            }

            return sum;
        }
};

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n,m,k; in(n,m,k);

    forn(i,1,n-1){
        int a, b; in(a, b);
        adj[a].emplace_back(b, i);
        adj[b].emplace_back(a, i);
    }

    dfs2();
    BinaryLift<int> BL(n);
    FenwickTree FT(n);


    forn(i,1,m){
        int g; in(g);
        vector<int> q;
        forn(j,1,g){
            int temp; in(temp);
            q.emplace_back(temp);
        }
        sort(q.begin(), q.end(), [](int a, int b){return tin[a] < tin[b];});
        if(g==1) continue;

        q.emplace_back(q[0]);

        forn(j,1,sz(q)-1){
            int c=tin[q[j-1]], d = tin[q[j]];
            int lc = BL.getLca(q[j], q[j-1]);
            int e = tin[lc];
            FT.update(c, 1);
            FT.update(d, 1);
            FT.update(e, -2);
        }
    }

    vector<int> fin;
    const int trg = 2*k;

    forn(i,2,n){
        int res = FT.print(tout[i])-FT.print(tin[i]-1);
        if(res>=2*k) fin.emplace_back(p_edge[i]);
    }

    sort(fin.begin(), fin.end());

    out(sz(fin));

    forn(i,0,sz(fin)-1){
        cout << fin[i] << " \n"[i==sz(fin)-1];
    }
    
    return 0;
}

Compilation message (stderr)

railway.cpp: In function 'int main()':
railway.cpp:164:15: warning: unused variable 'trg' [-Wunused-variable]
  164 |     const int trg = 2*k;
      |               ^~~

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