Submission #552722

#	Time	Username	Problem	Language	Result	Execution time	Memory
552722		Talha_Taki	Railway (BOI17_railway)	C++17	100 / 100	277 ms	34296 KiB

railway

#include <bits/stdc++.h>
 
using namespace std;
 
 
typedef long long ll;
typedef pair <int, int> pii;
 
 
vector <vector <int>> adj, parent;
vector <int> tin, tout, depth;
 
int x, timer;
 
struct Segment_Tree {
    int n;
    vector <int> tree;
 
    Segment_Tree() {}
    Segment_Tree(int n) : n(n) {
        tree.assign(n<<2, 0);
    }
 
    void update(int now, int l, int r, const int i, const int j) { // increment update
        if (l > j || r < i) return ;
        if (i <= l && j >= r) {
            tree[now]++;
            return ;
        }
 
        int mid = (l+r)>>1;
        int left = now<<1;
        int right = left|1;
 
        update(left, l, mid, i, j);
        update(right, mid+1, r, i, j);
    }
 
    int query(int now, int l, int r, const int pos) {
        if (l == r) return tree[now];
        
        int mid = (l+r)>>1;
        int left = now<<1;
        int right = left|1;
 
        if (pos <= mid) return tree[now] + query(left, l, mid, pos);
        else return tree[now] + query(right, mid+1, r, pos);
    }
};
 
void dfs(int u, int p) {
    tin[u] = ++timer;
    depth[u] = depth[p] + 1;
    parent[u][0] = p;
 
    for(int i = 1; i <= x; ++i) parent[u][i] = parent[parent[u][i-1]][i-1];
 
    for(int v : adj[u]) {
        if (v == p) continue;
        dfs(v, u);
    }
 
    tout[u] = ++timer;
}
 
inline bool isAncestor(int u, int v) {
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}
 
int lca(int u, int v) {
    if (isAncestor(u, v)) return u;
    if (isAncestor(v, u)) return v;
 
    for(int i = x; i >= 0; --i) {
        if (!isAncestor(parent[u][i], v)) {
            u = parent[u][i];
        }
    }
 
    return parent[u][0];
}
 
int upper(int u, int v) {
    if (depth[u] > depth[v]) swap(u, v);
 
    for(int i = x; i >= 0; --i) {
        if (!isAncestor(parent[v][i], u)) {
            v = parent[v][i];
        }
    }
    return v;
}
 
inline bool cmp(int u, int v) {
    return tin[u] < tin[v];
}
 
inline pii manage(int u, int v) {
    if (u > v) swap(u, v);
    return make_pair(u, v);
}
 
int main(const int argc, const char *argv[]) {
 
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n, m, k;
    cin >> n >> m >> k;
    int euler = n<<1;
 
    x = ceil(log2(n));
    timer = 0;
    adj.resize(n+1);
    parent.assign(n+1, vector <int> (x+1, 0));
    tin.resize(n+1);
    tout.resize(n+1);
    depth.assign(n+1, 0);
    tin[0] = 0;
    tout[0] = euler+1;
 
    map <pii, int> mp;
 
    for(int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
 
        adj[u].push_back(v);
        adj[v].push_back(u);

        mp[manage(u, v)] = i;
    }
    dfs(1, 0);
    Segment_Tree seg_tree(euler+1);
 
    for(int i = 0; i < m; ++i) {
        int s;
        cin >> s;
 
        vector <int> node(s);
        for(int i = 0; i < s; ++i) {
            cin >> node[i];
        }
        sort(node.begin(), node.end(), cmp);
 
        for(int i = 1; i < s; ++i) {
            node.push_back(lca(node[i], node[i-1]));
        }
 
        sort(node.begin(), node.end());
        node.resize(distance(node.begin(), unique(node.begin(), node.end())));
        sort(node.begin(), node.end(), cmp);
        s = node.size();
        
        vector <int> tmp;
        tmp.push_back(node[0]);
 
        for(int i = 1; i < s; ++i) {
            while (tmp.size() >= 2 && !isAncestor(tmp.back(), node[i])) {
                int u = tmp[tmp.size()-2];
                int v = tmp.back();
                assert(isAncestor(u, v));
                int a = upper(u, v);
                seg_tree.update(1, 1, euler, tin[a], tin[v]);
                tmp.pop_back();
            }
            tmp.push_back(node[i]);
        }
 
        while (tmp.size() > 1)  {
            int u = tmp[tmp.size()-2];
            int v = tmp.back();
            assert(isAncestor(u, v));
            int a = upper(u, v);
            seg_tree.update(1, 1, euler, tin[a], tin[v]);
            tmp.pop_back();
        }
    }
 
    int ans = 0;
    vector <int> id;
    for(int i = 2; i <= n; ++i) {
        int res = seg_tree.query(1, 1, euler, tin[i]) - seg_tree.query(1, 1, euler, tout[i]);
        if (res >= k) {
            ans++;
            id.push_back(mp[manage(parent[i][0], i)]);
        }
    }
    cout << ans << '\n';
 
    sort(id.begin(), id.end());
    for(int i : id) {
        cout << i << ' ';
    }
 
    return 0;
}

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