Submission #490901

#	Time	Username	Problem	Language	Result	Execution time	Memory
490901		MohammadAghil	Railway (BOI17_railway)	C++14	100 / 100	182 ms	42248 KiB

railway

#include <bits/stdc++.h> 
// #pragma GCC optimize ("Ofast")
// #pragma GCC target ("avx,avx2")
using namespace std; 
typedef long long ll; 
typedef pair<int, int> pp;
#define rep(i,l,r) for(int i = (l); i < r; i++)
#define per(i,r,l) for(int i = (r); i >= l; i--)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define pb push_back
#define ff first
#define ss second 

const ll mod = 1e9 + 7, maxn = 2e5 + 2, inf = 1e9 + 5;

map<int, int> st[maxn];
int s[maxn], k;
vector<int> ro[maxn], ans;
vector<pp> adj[maxn];

void dfs(int r, int p){
    for(pp c: adj[r]) if(c.ff != p){
        dfs(c.ff, r);
        if(sz(st[c.ff]) >= k) ans.pb(c.ss);
        if(sz(st[r]) < sz(st[c.ff])) st[r].swap(st[c.ff]);
        for(auto t: st[c.ff]){
            st[r][t.ff] += t.ss;
            if(st[r][t.ff] == s[t.ff]) st[r].erase(t.ff);
        }
        st[c.ff].clear();
    }
    for(int c: ro[r]){
        st[r][c]++;
        if(st[r][c] == s[c]) st[r].erase(c);
    }
}

int main(){
    cin.tie(0) -> sync_with_stdio(false);
    int n, m; cin >> n >> m >> k;
    rep(i,0,n-1){
        int u, v; cin >> u >> v; u--, v--;
        adj[u].pb({v, i});
        adj[v].pb({u, i});
    }
    rep(i,0,m){
        cin >> s[i];
        rep(j,0,s[i]){
            int u; cin >> u; u--;
            ro[u].pb(i);
        }
    } dfs(0, 0);
    sort(all(ans));
    cout << sz(ans) << '\n';
    for(int c: ans) cout << ++c << ' ';
    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