Submission #197160

#	Time	Username	Problem	Language	Result	Execution time	Memory
197160		dndhk	Railway (BOI17_railway)	C++14	100 / 100	174 ms	24976 KiB

railway

#include <bits/stdc++.h>

#define pb push_back

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const ll INF = 1000000000;
const int MAX_N = 100000;
const int MAX_K = 20;

int N, M, K;
vector<int> gp[MAX_N+1];
int lv[MAX_N+1], up[MAX_N+1][MAX_K+1], p[MAX_N+1];
int in[MAX_N+1], out[MAX_N+1], cnt;
int dp[MAX_N+1];
vector<pii> edge;

void dfs(int x){
	in[x] = ++cnt;
	up[x][0] = p[x];
	for(int i=1; i<MAX_K; i++){
		up[x][i] = up[up[x][i-1]][i-1];
	}
	for(int i : gp[x]){
		if(i==p[x])	continue;
		lv[i] = lv[x]+1;
		p[i] = x;
		dfs(i);
	}
	out[x] = ++cnt;
}

int lca(int x, int y){
	for(int i=MAX_K-1; i>=0; i--){
		if(lv[up[x][i]]>=lv[y]){
			x = up[x][i];
		}
		if(lv[up[y][i]]>=lv[x]){
			y = up[y][i];
		}
	}
	if(x==y)	return x;
	for(int i=MAX_K-1; i>=0; i--){
		if(up[x][i]!=up[y][i]){
			x = up[x][i];
			y = up[y][i];
		}
	}
	return up[x][0];
}

vector<int> v;
bool sf(int x, int y){
	return in[x]<in[y];
}
vector<int> ans;

void dfs2(int x){
	for(int i : gp[x]){
		if(i==p[x])	continue;
		dfs2(i);
		dp[x]+=dp[i];
	}
}

int main(){
	scanf("%d%d%d", &N, &M, &K);
	for(int i=1; i<N; i++){
		int a, b;
		scanf("%d%d", &a, &b);
		edge.pb({a, b});
		gp[a].pb(b); gp[b].pb(a);
	}
	lv[1] = 1; dfs(1);
	for(int i=1; i<=M; i++){
		int sz; scanf("%d", &sz);
		while(!v.empty())	v.pop_back();
		while(sz--){
			int x; scanf("%d", &x);
			v.pb(x);
		}
		sort(v.begin(), v.end(), sf);
		int r = v[0];
		for(int i=0; i<v.size()-1; i++){
			int l = lca(v[i], v[i+1]);
			if(lv[l]>=lv[r]){
				dp[v[i+1]]++;
				dp[l]--;
			}else{
				dp[r]++;
				dp[v[i+1]]++;
				dp[l]-=2;
				r = l;
			}
		}
	}
	dfs2(1);
	// for(int i=1; i<=N; i++){
	// 	cout<<i<<" "<<p[i]<<" "<<dp[i]<<endl;
	// }
	for(int i=0; i<edge.size(); i++){
		if(p[edge[i].first]==edge[i].second && dp[edge[i].first]>=K){
			ans.pb(i+1);
		}else if(p[edge[i].second]==edge[i].first && dp[edge[i].second]>=K){
			ans.pb(i+1);
		}
	}
	printf("%d\n", (int)ans.size());
	for(int i=0; i<ans.size(); i++){
		printf("%d ", ans[i]);
	}
}

Compilation message (stderr)

railway.cpp: In function 'int main()':
railway.cpp:88:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<v.size()-1; i++){
                ~^~~~~~~~~~~
railway.cpp:105:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<edge.size(); i++){
               ~^~~~~~~~~~~~
railway.cpp:113:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<ans.size(); i++){
               ~^~~~~~~~~~~
railway.cpp:71:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &N, &M, &K);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
railway.cpp:74:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~
railway.cpp:80:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int sz; scanf("%d", &sz);
           ~~~~~^~~~~~~~~~~
railway.cpp:83:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int x; scanf("%d", &x);
           ~~~~~^~~~~~~~~~

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