Submission #208061

#	Time	Username	Problem	Language	Result	Execution time	Memory
208061		ly20	Railway (BOI17_railway)	C++17	100 / 100	266 ms	37128 KiB

railway

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 112345, MAXK = 20;
int t;
vector < int > grafo[MAXN];
int marc[MAXN], dp[MAXN][MAXK], prof[MAXN];
int id[MAXN];
void dfs(int v, int p) {
	dp[v][0] = p;
	t++;
	id[v] = t;
	for(int i = 0; i < grafo[v].size(); i++) {
		int viz = grafo[v][i];
		if(viz == p) continue;
		prof[viz] = prof[v] + 1;
		dfs(viz, v);
	}
}
int lca(int a, int b) {
	if(prof[a] > prof[b]) swap(a, b);
	int d = prof[b] - prof[a];
	for(int i = 0; i < MAXK; i++) {
		if((1 << i) & d) b = dp[b][i];
	}
	if(a == b) return a;
	for(int i = MAXK - 1; i >= 0; i--) {
		if(dp[a][i] != dp[b][i]) {
			a = dp[a][i]; b = dp[b][i];
		}
	}
	return dp[a][0];
}
void dfs2(int v, int p) {
	for(int i = 0; i < grafo[v].size(); i++) {
		int viz = grafo[v][i];
		if(viz == p) continue;
		dfs2(viz, v);
		marc[v] += marc[viz];
	}
}
bool cmp(int a, int b) {
	return id[a] < id[b];
}
map < pair < int, int >, int > mp;
int main() {
	int n, m, k;
	scanf("%d %d %d", &n, &m, &k);
	for(int i = 0; i < n - 1; i++) {
		int a, b;
		scanf("%d %d", &a, &b); a--; b--;
		grafo[a].push_back(b); grafo[b].push_back(a);
		mp[make_pair(a, b)] = i + 1; mp[make_pair(b, a)] = i + 1;
	}
	dfs(0, 0);
	for(int i = 1; i < MAXK; i++) {
		for(int j = 0; j < n; j++) {
			dp[j][i] = dp[dp[j][i - 1]][i - 1];
		}
	}
	for(int i = 0; i < m; i++) {
		int s;
		scanf("%d", &s);
		vector < int > v;
		for(int j = 0; j < s; j++) {
			int a;
			scanf("%d", &a); a--;
			marc[a]++;
			v.push_back(a);
		}
		sort(v.begin(), v.end(), cmp);
		for(int j = 1; j < s; j++) {
			//printf("%d %d\n", v[j], v[j - 1]);
			marc[lca(v[j], v[j - 1])]--;
		}
		marc[lca(v[0], v[s - 1])]--;
	}
	dfs2(0, 0);
	vector < int > resp;
	for(int i = 0; i < n; i++) {
		if(marc[i] >= k) resp.push_back(mp[make_pair(i, dp[i][0])]);
	}
	sort(resp.begin(), resp.end());
	printf("%d\n", resp.size());
	for(int i = 0; i < resp.size(); i++) {
		printf("%d ", resp[i]);
	}
	printf("\n");
	return 0;
}

Compilation message (stderr)

railway.cpp: In function 'void dfs(int, int)':
railway.cpp:12:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < grafo[v].size(); i++) {
                 ~~^~~~~~~~~~~~~~~~~
railway.cpp: In function 'void dfs2(int, int)':
railway.cpp:34:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < grafo[v].size(); i++) {
                 ~~^~~~~~~~~~~~~~~~~
railway.cpp: In function 'int main()':
railway.cpp:83:28: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
  printf("%d\n", resp.size());
                 ~~~~~~~~~~~^
railway.cpp:84:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < resp.size(); i++) {
                 ~~^~~~~~~~~~~~~
railway.cpp:47: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:50:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &a, &b); a--; b--;
   ~~~~~^~~~~~~~~~~~~~~~~
railway.cpp:62:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &s);
   ~~~~~^~~~~~~~~~
railway.cpp:66:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &a); a--;
    ~~~~~^~~~~~~~~~

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