Submission #948335

#	Time	Username	Problem	Language	Result	Execution time	Memory
948335		steveonalex	Railway (BOI17_railway)	C++14	100 / 100	136 ms	45360 KiB

railway

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
#define MASK(i) (1LL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()
 
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
 
ll LASTBIT(ll mask){return (mask) & (-mask);}
int pop_cnt(ll mask){return __builtin_popcountll(mask);}
int ctz(ll mask){return __builtin_ctzll(mask);}
int logOf(ll mask){return 63 - __builtin_clzll(mask);}
 
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rngesus(ll l, ll r){return l + (ull) rng() % (r - l + 1);}
 
template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if (a < b) {a = b; return true;}
        return false;
    }
 
template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if (a > b) {a = b; return true;}
        return false;
    }
 
template <class T>
    void printArr(T container, char separator = ' ', char finish = '\n'){
        for(auto item: container) cout << item << separator;
        cout << finish;
    }
 template <class T>
    void remove_dup(vector<T> &a){
        sort(ALL(a));
        a.resize(unique(ALL(a)) - a.begin());
    }
 
const long N = 1e5 + 69;
const long LOG_N = 17;
long n, m, k;
map<pair<long, long>, long> mp;
vector<long> graph[N];
long sum[N];
 
long h[N], parent[N][LOG_N], in[N], pos[N];
long dfs_cnt = 0;
 
void dfs(long u, long p){
    in[u] = ++dfs_cnt; pos[dfs_cnt] = u;
    h[u] = (u == p) ? 1 : (h[p] + 1);
    for(long j = 1; MASK(j) < h[u]; ++j) parent[u][j] = parent[parent[u][j-1]][j-1];
    for(long v: graph[u]) if (v != p){
        parent[v][0] = u;
        dfs(v, u);
    }
}
 
long LCA(long u, long v){
    if (h[u] < h[v]) swap(u, v);
    long diff = h[u] - h[v];
    for(long j = 0; j<LOG_N; ++j) if (GETBIT(diff, j)) u = parent[u][j];
    if (u == v) return u;
    for(long j = LOG_N - 1; j>=0; --j) if (parent[u][j] != parent[v][j]){
        u = parent[u][j]; v = parent[v][j];
    }
    return parent[u][0];
}
 
vector<long> ans;
 
void calc(long u, long p){
    for(long v: graph[u]) if (v != p){
        calc(v, u);
        sum[u] += sum[v];
 
        if (sum[v] >= k){
            long x = u, y = v;
            if (x > y) swap(x, y);
            ans.push_back(mp[{x, y}]);
        }
    }
}
 
int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
    cin >> n >> m >> k;
    for(long i = 1; i<n; ++i){
        long u, v; cin >> u >> v;
        if (u > v) swap(u, v);
        graph[u].push_back(v);
        graph[v].push_back(u);
        mp[{u, v}] = i;
    }
 
    dfs(1, 1);
 
    while(m--){
        long s; cin >> s;
        vector<long> ver(s);
        for(long i = 0; i<s; ++i){
            cin >> ver[i];
            ver[i] = in[ver[i]];
        }
        remove_dup(ver);
 
        s = ver.size();
        for(long i = 1; i < s; ++i) ver.push_back(in[ LCA(pos[ver[i-1]], pos[ver[i]]) ]);
 
        remove_dup(ver);
        for(long &i: ver) i = pos[i];
        reverse(ALL(ver));
 
        vector<long> st;
        for(long u: ver){
            while(st.size()){
                long v = st.back();
                if (LCA(u, v) == u){
                    sum[u]--;
                    sum[v]++;
                    st.pop_back();
                    continue;
                }
                else break;
            }
            st.push_back(u);
        }
    }
 
    calc(1, 1);
 
    cout << ans.size() << "\n";
    sort(ALL(ans));
    printArr(ans);
 
 
    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