Submission #869652

#	Time	Username	Problem	Language	Result	Execution time	Memory
869652		ArashJafariyan	Railway (BOI17_railway)	C++17	0 / 100	1044 ms	40016 KiB

railway

#include <bits/stdc++.h>
using namespace std;
using pii = array<int, 2>;
using piii = array<int, 3>;

#define pb push_back

const int LG = 16 + 2, N = 1e5 + 4;

int n, m, k, cnt[N];
set<piii> sack; // {dep, startingVertex, visited}

struct Node {
    int h, e, bc, anc[LG];
    vector<int> dep;
    vector<pii> adj;
} g[N];

int prepare(int v = 0, int p = 0) {
    if (!v)
        g[v].anc[0] = -1;
    for (int i = 1; i < LG; ++i) {
        int u = g[v].anc[i - 1];
        if (u != -1) 
            g[v].anc[i] = g[u].anc[i - 1];
        else 
            g[v].anc[i] = -1;
    }

    g[v].bc = -1;
    int ret = 1, curMax = 0;
    for (auto [u, idxE] : g[v].adj) {
        if (u != p) {
            g[u].h = g[v].h + 1;
            g[u].e = idxE;
            g[u].anc[0] = v;

            int res = prepare(u, v);
            ret += res;
            if (res > curMax) {
                curMax = res;
                g[v].bc = u; 
            }
        }
    }
    return ret;
}

int anc(int v, int dis) {
    for (int i = 0; i < LG; ++i) 
        if ((1 << i) & dis) 
            v = g[v].anc[i];
    return v;
}

void del(int v, int p) {
    for (int dep : g[v].dep) {
        auto pt = sack.lower_bound({dep, -1, -1});
        sack.erase(pt);
    }

    for (auto [u, idxE] : g[v].adj) 
        if (u != p)
            del(u, v);
}

void add(int v, int p, int r) {
    for (int dep : g[v].dep) {
        auto pt = sack.lower_bound({dep, -1, -1});
        piii t;

        if (pt != sack.end()) {
            t = *pt;
            if (t[2] == r) {
                int w = anc(v, g[v].h - g[r].h - 1);
                ++cnt[g[w].e];
            }
            else {
                int w = anc(v, g[v].h - g[r].h - 1);
                ++cnt[g[w].e];

                w = (t[1], g[t[1]].h - g[r].h - 1);
                ++cnt[g[w].e];
                sack.erase(pt);
                t[2] = r;
                sack.insert(t);
            }
        }
    }

    for (auto [u, idxE] : g[v].adj) 
        if (u != p)
            add(u, v, r);
}

void dfs(int v = 0, int p = 0) {
    for (auto [u, idxE] : g[v].adj) {
        if (u != p && u != g[v].bc) {
            dfs(u, v);
            del(u, v);
        }
    }

    if (g[v].bc != -1) 
        dfs(g[v].bc, v);
    for (auto [u, idxE] : g[v].adj) 
        if (u != p && u != g[v].bc) 
            add(u, v, v);

    for (int dep : g[v].dep) {
        auto pt = sack.lower_bound({dep, -1, -1});
        
        if (pt != sack.end()) {
            piii t = *pt;
            if (t[2] != v) {
                int w = anc(t[1], g[t[1]].h - g[v].h - 1);
                ++cnt[g[w].e];
                
                sack.erase(pt);
                t[2] = v;
                sack.insert(t);
            }
        }
    }
    for (int dep : g[v].dep) 
        sack.insert({dep, v, -1});
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m >> k;
    for (int i = 0; i < n - 1; ++i) {
        int v, u;
        cin >> v >> u;
        --v, --u;
        g[v].adj.pb({u, i});
        g[u].adj.pb({v, i});
    }
    for (int i = 0; i < m; ++i) {
        int s;
        cin >> s;
        while (s--) {
            int v;
            cin >> v;
            --v;
            g[v].dep.pb(i);
        }
    }

    prepare();
    dfs();

    vector<int> out;
    for (int i = 0; i < n - 1; ++i) {
        if (cnt[i] >= k) {
            out.pb(i);
        }
        cout << cnt[i] << ' ';
    }
    cout << '\n';

    cout << out.size() << '\n';
    for (int edge : out)
        cout << edge + 1 << ' ';

    return 0;
}

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