Submission #480704

#	Time	Username	Problem	Language	Result	Execution time	Memory
480704		hidden1	Railway (BOI17_railway)	C++14	100 / 100	167 ms	36648 KiB

railway

#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;}
template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;
#ifndef LOCAL
#define cerr if(false) cerr
#endif

const ll MAX_N = 1e5 + 10, MAX_LOG = 20;;
vector<pair<ll, ll> > g[MAX_N];
ll par[MAX_N][MAX_LOG];
ll d[MAX_N];
ll ind[MAX_N], cnt[MAX_N];
ll in[MAX_N], out[MAX_N], tme; 
vector<ll> ans;
ll n, m, k;

void dfs(ll x, ll p) {
    par[x][0] = p;
    for(ll i = 1; i < MAX_LOG; i ++) {
        par[x][i] = par[par[x][i - 1]][i - 1];
    }
    d[x] = d[p] + 1;
    in[x] = out[x] = tme ++;
    for(auto it : g[x]) {
        if(it.first == p) {continue;}
        ind[it.first] = it.second;
        dfs(it.first, x);
        out[x] = out[it.first];
    }
}

ll lca(ll a, ll b) {
    if(d[a] < d[b]) {swap(a, b);}
    for(ll i = MAX_LOG - 1; i >= 0; i --) {
        if(d[par[a][i]] >= d[b]) {
            a = par[a][i];
        }
    }
    if(a == b) {return a;}
    for(ll i = MAX_LOG - 1; i >= 0; i --) {
        if(par[a][i] != par[b][i]) {
            a = par[a][i];
            b = par[b][i];
        }
    }
    return par[a][0];
}

ll calc(ll x, ll p) {
    ll now = cnt[x];
    for(auto it : g[x]) {
        if(it.first == p) {continue;}
        now += calc(it.first, x);
    }
    if(now >= k) {
        ans.push_back(ind[x]);
    }
    cerr << "for " << x << " " << ind[x] << " " << now << endl;
    return now;
}

void addCnt(vector<ll> &vert) {
    sort(vert.begin(), vert.end(), [](const ll a, const ll b) {
        return in[a] < in[b];
    });
    for(auto it : vert) {
        cnt[it] ++;
    }

    vector<pair<ll, ll> > auxVert = {{vert[0], 1}};
    for(ll i = 1; i < vert.size(); i ++) {
        auxVert.push_back({lca(vert[i - 1], vert[i]), 0});
        auxVert.push_back({vert[i], 1});
    }
    sort(auxVert.begin(), auxVert.end(), [](const pair<ll, ll> &a, const pair<ll, ll> &b) {
        return in[a.first] < in[b.first];
    });

    stack<pair<ll, ll> > st;
    auto executePop = [](const pair<ll, ll> x) {
        cnt[x.first] -= x.second - 1; 
    };

    for(auto it : auxVert) {
        while(!st.empty() && !(in[st.top().first] <= in[it.first] && out[it.first] <= out[st.top().first])) {
            auto tp = st.top(); st.pop();
            executePop(tp);
            if(!st.empty()) {
                st.top().second ++;
            }
        }
        if(st.empty() || st.top().first != it.first) {
            st.push(it);
        } else {
            st.top().second += it.second;
        }
    }
    while(!st.empty()) {
        auto tp = st.top(); st.pop();
        executePop(tp);
        if(!st.empty()) {
            st.top().second ++;
        } else {
            cnt[tp.first] --;
        }     
    }
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    cin >> n >> m >> k;
    for(ll i = 0; i < n - 1; i ++) {
        ll a, b;
        cin >> a >> b;
        g[a].push_back({b, i + 1});
        g[b].push_back({a, i + 1});
    }
    dfs(1, 0);

    for(ll i = 0; i < m; i ++) {
        ll lst;
        cin >> lst;
        vector<ll> a(lst);
        for(ll j = 0; j < lst; j ++) {
            cin >> a[j];
        }
        addCnt(a);
    }
    calc(1, 0);

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

    cout << ans.size() << endl;
    for(auto it : ans) {
        cout << it << " ";
    }

    return 0;
}

Compilation message (stderr)

railway.cpp: In function 'void addCnt(std::vector<long long int>&)':
railway.cpp:79:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for(ll i = 1; i < vert.size(); i ++) {
      |                   ~~^~~~~~~~~~~~~

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