Submission #1310151

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310151		muhammad-mutahir	Railway (BOI17_railway)	C++20	0 / 100	161 ms	50756 KiB

railway

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

#define print(l) for(auto i:l) cout<<i<<" ";cout<<endl;
#define input(t,l,n) vector<t>l(n);for(int i = 0;i<n;i++)cin>>l[i];
#define int long long
#define pb push_back
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
#define all(l) l.begin(),l.end()
#define pii pair<int,int>
#define fi first
#define se second

const int N = 1e6+10;
const int lg  = log2(N)+1;
const int M = 1e9+7;
const int inf = 1e18;


void io(){
    #ifndef ONLINE_JUDGE
    freopen("cowland.in","r",stdin);
    freopen("cowland.out","w",stdout);
    #endif
}

int bp(int x, int y, int p){
    int res = 1;
    x = x % p;
    while (y > 0) {
 
        if (y & 1)
            res = (res * x) % p;
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}
 
int MI(int n, int p){
    return bp(n, p - 2, p);
}
int mul(int x,int y, int p){
    return x * 1ull * y % p;
}
int di(int x,int y, int p){
    return mul(x, MI(y, p), p);
}


int n , m , k , q;
int ti;
vector<vector<int>>adj;
vector<int>intime;
vector<int>dis,sum;

vector<int>ans;

int sp[N][lg];

void dfs(int v,int par){
	intime[v] = ti;
	ti++;
	sp[v][0] = par;
	
	for(int i:adj[v]){
		if(i == par){
			continue;
		}
		dis[i] = min(dis[i],dis[v]+1);
		dfs(i,v);
	}
}



int lca(int u,int v){
	if(dis[u] > dis[v] ){
		swap(u,v);
	}
	int d = dis[v]-dis[u];
	for(int i = lg-1;i>=0;i--){
		if(d&(1<<i)){
			v = sp[v][i];
			d-=(1<<i);
		}
	}
	if(u == v){
		return u;
	}
	for(int i = lg-1;i>=0;i--){
		if(sp[u][i] != sp[v][i]){
			u = sp[u][i];
			v = sp[v][i];
		}
	}
	// cout<<u<<" "<<v<<endl;
	return sp[v][0];
	
}


map<pair<int, int>, int> E;
vector<int> op;
int an;

void dfs1(int v,int par){
	sum[v] = ans[v];
    for (auto i : adj[v]){
        if (i == par) continue;
        dfs1(i,v);
        sum[v] += sum[i];
    }
    if (sum[v] >= k and v!= 1) {
    	an++;
    	// cout<<par<<" "<<v<<endl;
        op.push_back(E[{par, v}]);
    }
}


void solve(int testcase_number){
    cin>>n>>m>>k;
    an = 0;
    ti = 0;
    adj.resize(n+1);
    ans.resize(n+1,0);
    sum.resize(n+1,0);
    intime.resize(n+1);
    dis.resize(n+1,inf);

    for(int i = 0;i<n-1;i++){
    	int u,v;
    	cin>>u>>v;
    	E[{u,v}] = i+1;
    	E[{v,u}] = i+1;
    	adj[u].pb(v);
    	adj[v].pb(u);
    	// cout<<u<<" "<<v<<endl;
    }
    // print(adj[1]);
    dis[1] = 0;
    sp[1][0] = 1;
    intime[1] = 0;
    dfs(1,1);
    
    for(int i = 1;i<lg;i++){
    	for(int j = 1;j<=n;j++){
    		sp[j][i] = sp[sp[j][i-1]][i-1];
    	}
    }
    
    for(int i = 0;i<m;i++){
    vector<pair<int,int>>ord;
    	int sz;
    	cin>>sz;
    	input(int,st,sz);

    	for(int j:st){
    		ans[j]++;
    		ord.pb({intime[j],j});
    	}
    	sort(all(ord));
    	for(int i = 0;i+1<sz;i++){
    		ans[lca(ord[i].se,ord[i+1].se)]--;
    		
    	}
    	ans[lca(ord[0].se,ord.back().se)]--;
    	
    }
    dfs1(1,1);
    cout<<an<<endl;
    for(auto i:op){
    	cout<<i<<" ";
    }
    cout<<endl;


}


signed main(){
    ios::sync_with_stdio(0);//DO NOT USE IN INTERACTIVE
    cin.tie(0), cout.tie(0);
    cout << fixed<<setprecision(9);

    int t = 1;
    // cin>>t;
    for(int i = 1;i<=t;i++){
        solve(i);
    }

}

Compilation message (stderr)

railway.cpp: In function 'void io()':
railway.cpp:22:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |     freopen("cowland.in","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
railway.cpp:23:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |     freopen("cowland.out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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