Submission #205787

#	Time	Username	Problem	Language	Result	Execution time	Memory
205787		ly20	Railway (BOI17_railway)	C++17	23 / 100	1096 ms	34836 KiB

railway

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 112345, MAXK = 22;
int dp[MAXN][MAXK], prof[MAXN];
vector <int> grafo[MAXN];
void dfs(int v, int p) {
	dp[v][0] = p;
	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 = MAXK - 1; i >= 0; i--) {
		if(d >= (1 << i)) {
			b = dp[b][i];
			d -= (1 << 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];
}
map < pair < int, int >, int > mp;
int marc[MAXN], cont[MAXN];
bool dfs1(int v, int p) {
	//printf("%d\n", v);
	bool ok = false;
	if(marc[v] == 1) ok = true;
	for(int i = 0; i < grafo[v].size(); i++) {
		int viz = grafo[v][i];
		//printf("%d %d\n", v, viz);
		if(viz == p) continue;
		//printf("oi\n");
		if(dfs1(viz, v)) ok = true;
	}
	if(ok) {
		cont[v]++;
		//printf("%d++\n", v);
	}
	return ok;
}
int main() {
	int n, m, k;
	scanf("%d %d %d", &n, &m, &k);
	for(int i = 1; i < n; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		grafo[a].push_back(b); grafo[b].push_back(a);
		mp[make_pair(a, b)] = i; mp[make_pair(b, a)] = i;
	}
	dfs(1, 1);
	for(int i = 1; i < MAXK; i++) {
		for(int j = 1; j <= n; j++) {
			dp[j][i] = dp[dp[j][i - 1]][i - 1];
		}
	}
	for(int i = 0; i < m; i++) {
		vector < int > v;
		int a;
		scanf("%d", &a);
		int lc;
		scanf("%d", &lc);
		v.push_back(lc);
		marc[lc] = 1;
		for(int j = 1; j < a; j++) {
			int b;
			scanf("%d", &b);
			marc[b] = 1;
			v.push_back(b);
			lc = lca(lc, b);
		}
		//printf("%d\n", lc);
		dfs1(lc, lc);
		cont[lc]--;
		for(int j = 0; j < a; j++) {
			marc[v[j]] = 0;
		}
		v.clear();
	}
	vector <int> v;
	for(int i = 1; i <= n; i++) {
		if(cont[i] >= k) v.push_back(mp[make_pair(i, dp[i][0])]);
	}
	printf("%d\n", v.size());
	sort(v.begin(), v.end());
	for(int i = 0; i < v.size() ; i++) printf("%d ", v[i]);
	printf("\n");
	return 0;
}

Compilation message (stderr)

railway.cpp: In function 'void dfs(int, int)':
railway.cpp:8:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < grafo[v].size(); i++) {
                 ~~^~~~~~~~~~~~~~~~~
railway.cpp: In function 'bool dfs1(int, int)':
railway.cpp:38: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:93:25: 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", v.size());
                 ~~~~~~~~^
railway.cpp:95:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < v.size() ; i++) printf("%d ", v[i]);
                 ~~^~~~~~~~~~
railway.cpp:53: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:56: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:69:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a);
   ~~~~~^~~~~~~~~~
railway.cpp:71:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &lc);
   ~~~~~^~~~~~~~~~~
railway.cpp:76:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &b);
    ~~~~~^~~~~~~~~~

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