Submission #1105134

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105134		nguyenhainam1012	Railway (BOI17_railway)	C++17	100 / 100	163 ms	50880 KiB

railway

#include <bits/stdc++.h>
using namespace std;
#define ll long long
/*
#pragma omp
#pragma simd
#pragma unroll
#pragma pack
#pragma GCC optimize(3)
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC target("avx","sse2")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
*/
#define int long long
#define fi first
#define se second
#define pb push_back
#define M_PI 3.14159265358979323846
#define set_on(x, i) ((x) | (1 << i))
#define set_off(x, i) ((x) & ~(1 << i))
#define get_bit(x, i) ((x >> i) & 1)
#define count_bit(x) __builtin_popcountll(x)
#define rep(i, a, b) for(int i=a; i<b; i++)
const int maxn=1e6+5;
const int mxn=1e7+5;
const int N =1e5+5;
int base=313,basej=431;
ll MOD=790972;//
int mod=1e9+7;
int inf=1e17;
typedef pair<int, int> pii;
const int S = 19;
const int LOG = log2(N)+1;
// ll sqr(ll x) {
//     return x*x;
// }
// ll power(ll a, ll b) {
//     if (b == 0) return 1 % mod;

//         if (b % 2 == 0)
//             return sqr(power(a, b/2)) % mod;
//                 return a * (sqr(power(a, b/2)) % mod) % mod;}
int n,depth[N],f[N][18],in[N],cur=0,m,k,ps[N];
map<pii,int>mp;
vector<int>adj[N];
vector<int>ans;
void dfs(int u,int p){
    in[u]=++cur; f[u][0]=p; depth[u]=depth[p]+1;
    for(int i=1;i<=17;i++)f[u][i]=f[f[u][i-1]][i-1];
    for(auto v:adj[u]){
        if(v==p)continue;
        dfs(v,u);
    }
}
int lca(int u,int v){
    if(depth[u]<depth[v])swap(u,v);
    for(int i=17;i>=0;i--){
        if(depth[f[u][i]]>=depth[v])u=f[u][i];
    }
    if(u==v)return u;
    for(int i=17;i>=0;i--){
        if(f[u][i]!=f[v][i]){
            u=f[u][i];v=f[v][i];
        }
    }
    return f[u][0];
}
bool check_par(int u,int p){
    for(int i=17;i>=0;i--){
        if(depth[f[u][i]]>=depth[p])u=f[u][i];
    }
    return (u==p);
}
void dfs2(int u,int p){
    for(auto v:adj[u]){
        if(v==p)continue;
        dfs2(v,u);
        ps[u]+=ps[v];
        if(ps[v]>=k)ans.pb(mp[{u,v}]);
    }
}
bool cmp(int u,int v){
return in[u]<in[v];}
void solve(){
    dfs(1,0);
    while(m--){
        int sl;cin >> sl;
        vector<int>v;
        for(int i=0;i<sl;i++){
            int x;cin >> x; v.pb(x);
        }
        sort(v.begin(),v.end(),cmp);
        for(int i=0;i<sl-1;i++){
            v.pb(lca(v[i],v[i+1]));
        }
        sort(v.begin(),v.end(),cmp);v.erase(unique(v.begin(),v.end()),v.end());
        vector<int>s;
        s.pb(v[0]);
        int pos=1;
        while(pos<(int)v.size()){
            while((int)s.size()>=0 && check_par(v[pos],s.back())==0){
                s.pop_back();
            }
            ps[v[pos]]++; ps[s.back()]--;
            //cout << v[pos] << " "<<s.back() << '\n';
            s.pb(v[pos]);
            pos++;
         }
    }
    dfs2(1,0); sort(ans.begin(),ans.end());cout << ans.size() << '\n';
    for(auto x:ans)cout << x << " ";
}
void input(){
     cin >> n >> m >> k ;
     for(int i=1;i<n;i++){
        int u,v;cin >> u >> v;
        adj[u].pb(v); adj[v].pb(u);
        mp[{u,v}]=i; mp[{v,u}]=i;
     }
}
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(NULL); cout.tie(NULL);
// 	if (fopen("IMPEVAL.inp", "r")) {
// 		freopen("IMPEVAL.inp", "r", stdin);
// 		freopen("IMPEVAL.out", "w", stdout);
// 	}

    int t;t=1;
    while(t--){
        input();
        solve();
    }
}

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