Submission #677759

#	Time	Username	Problem	Language	Result	Execution time	Memory
677759		HaYoungJoon	Railway (BOI17_railway)	C++14	100 / 100	159 ms	23748 KiB

railway

#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> pii;
const int maxn = 1e5 + 1;
const int LOG = 16;
int n,m,k, timer = 0, mark[maxn];
vector<pii> adj[maxn];
int tin[maxn], tout[maxn],up[LOG+1][maxn], node[maxn], bit[maxn], E[maxn];

void DFS(int u, int p) {
    tin[u] = ++timer;
    node[tin[u]] = u;
    up[0][u] = p;
    for (int i = 1; i <= LOG; i++) up[i][u] = up[i-1][up[i-1][u]];
    for (pii i: adj[u]) {
        int v = i.first, id = i.second;
        if (v == p) continue;
        E[v] = id;
        DFS(v,u);
    }
    tout[u] = timer;
}

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 = LOG; i >= 0; i--)
        if (!is_ancestor(up[i][u],v)) u = up[i][u];
    return up[0][u];
}

bool cmp(int A, int B) {
    return tin[A] < tin[B];
}


void update(int idx, int val) {
    for (; idx <= n; idx += (idx & -idx)) bit[idx] += val;
}
int getSum(int L, int R) {
    L--;
    int res = 0;
    for (; L > 0; L -= (L & -L)) res -= bit[L];
    for (; R > 0; R -= (R & -R)) res += bit[R];
    return res;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m >> k;
    for (int i = 1; i < n; i++) {
        int u,v;
        cin >> u >> v;
        adj[u].push_back(pii(v,i));
        adj[v].push_back(pii(u,i));
    }
    DFS(1,1);
    while (m--) {
        int Q;
        cin >> Q;
        for (int i = 1; i <= Q; i++) cin >> mark[i];
        sort(mark+1,mark+1+Q,cmp);
        mark[Q+1] = mark[1];
        for (int i = 1; i <= Q; i++) {
            int L = LCA(mark[i],mark[i+1]);
            update(tin[mark[i]],1);
            update(tin[mark[i+1]],1);
            update(tin[L],-2);
        }
    }
    vector<int> res;
    for (int i = 2; i <= n; i++)
        if (getSum(tin[i],tout[i]) >= 2*k) res.push_back(E[i]);
    sort(res.begin(),res.end());
    cout << res.size() << '\n';
    for (int i: res) cout << i << ' ';
    return 0;
}
/*
6 1 2
1 3
2 3
3 4
6 4
4 5
4 1 3 2 5
*/

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