Submission #501940

#	Time	Username	Problem	Language	Result	Execution time	Memory
501940		Lobo	Railway (BOI17_railway)	C++17	30 / 100	474 ms	16312 KiB

railway

#include<bits/stdc++.h>
using namespace std;

/*for ordered_set
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<pair<int,int>, null_type,less<pair<int,int>>, rb_tree_tag,tree_order_statistics_node_update>
*/

const long long INFll = (long long) 1e18 + 10;
const int INFii = (int) 1e9 + 10;
typedef long long ll;
typedef int ii;
typedef long double dbl;
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

#define maxn 110000

ii n, m, k, cnt[maxn], bit[maxn];
vector<pair<ii,ii>> edg, g[maxn];
ii tin[maxn], tout[maxn], timer = 1;

void att(ii pos, ii val) {
    for(ii i = pos; i <= n; i+= i&-i) {
        bit[i]+= val;
    }
}

ii qr(ii pos) {
    ii val = 0;
    for(ii i = pos; i > 0; i-= i&-i) {
        val+= bit[i];
    }
    return val;
}

void dfst(ii u, ii ant, ii id) {
    //.fr = pai .sc = filho
    if(u != 1 && edg[id].fr == u) swap(edg[id].fr,edg[id].sc);

    tin[u] = timer++;

    for(auto V : g[u]) {
        ii v = V.fr;
        ii id1 = V.sc;
        if(v == ant) continue;
        
        dfst(v,u,id1);
    }

    tout[u] = timer-1;
}

void solve() {
    cin >> n >> m >> k;

    for(ii i = 0; i < n-1; i++) {
        ii a, b;
        cin >> a >> b;

        g[a].pb(mp(b,i));
        g[b].pb(mp(a,i));
        edg.pb(mp(a,b));
    }

    dfst(1,0,0);

    if(n <= 10000 && m <= 2000) {

        for(ii i = 0; i < m; i++) {
            ii s; cin >> s;
            vector<ii> v;
            for(ii j = 0; j < s; j++) {
                ii u; cin >> u;
                v.pb(u);
                att(tin[u],+1);
            }

            for(ii i = 0; i < n-1; i++) {
                ii u = edg[i].fr;
                ii v = edg[i].sc;

                ii sum = qr(tout[v]) - qr(tin[v]-1);

                if(sum != 0 && sum-s != 0) cnt[i]++;
            }

            for(auto u : v) att(tin[u],-1);
        }
    

    }
    else {
        for(ii i = 0; i < m; i++) {
            ii s; cin >> s;
            vector<ii> v;
            ii mn = n+1;
            ii mx = 0;
            for(ii j = 0; j < s; j++) {
                ii u; cin >> u;
                mn = min(mn,tin[u]);
                mx = max(mx,tin[u]);
            }

            att(mn,+1);
            att(mx,-1);
        }

        for(ii i = 0; i < n-1; i++) {
            ii u = edg[i].fr;
            ii v = edg[i].sc;

            cnt[i] = qr(tin[u]);
        
        }
    }
    

    vector<ii> ans;
    for(ii i = 0; i < n-1; i++) {
        if(cnt[i] >= k) ans.pb(i+1);
    }

    cout << ans.size() << endl;
    for(auto x : ans) cout << x << " ";
    cout << endl;

}

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

    // freopen("in.in", "r", stdin);
    //freopen("out.out", "w", stdout);

    ii tt = 1;
    // cin >> tt;
    while(tt--) solve();

}

Compilation message (stderr)

railway.cpp: In function 'void solve()':
railway.cpp:86:20: warning: unused variable 'u' [-Wunused-variable]
   86 |                 ii u = edg[i].fr;
      |                    ^
railway.cpp:117:16: warning: unused variable 'v' [-Wunused-variable]
  117 |             ii v = edg[i].sc;
      |                ^

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