Submission #205790

#	Time	Username	Problem	Language	Result	Execution time	Memory
205790		ly20	Railway (BOI17_railway)	C++17	7 / 100	199 ms	27504 KiB

railway

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 112345, MAXK = 22;
int id[MAXN], inv[MAXN];
vector <int> grafo[MAXN];
map < pair < int, int >, int > mp;
int t;
int seg[4 * MAXN];
void dfs(int v, int p) {
	id[v] = t; inv[t] = v;
	t++;
	for(int i = 0; i < grafo[v].size(); i++) {
		int viz = grafo[v][i];
		if(viz == p) continue;
		dfs(viz, v);
	}
}
void update(int cur, int ini, int fim, int a, int b) {
	if(ini > b || fim < a) return;
	if(ini >= a && fim <= b) {
		seg[cur]++;
		return;
	}
	int m = (ini + fim) / 2;
	int e = 2 * cur, d = 2 * cur + 1;
	update(e, ini, m, a, b); update(d, m + 1, fim, a, b);
}
int query(int cur, int ini, int fim, int id) {
	if(ini > id || fim < id) return 0;
	if(ini == fim) return seg[cur];
	int m = (ini + fim) / 2;
	int e = 2 * cur, d = 2 * cur + 1;
	return query(e, ini, m, id) + query(d, m + 1, fim, id) + seg[cur];
}
int main() {
	t = 1;
	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;
	}
	for(int i = 1; i <= n; i++) {
		if(grafo[i].size() == 1)  {
			dfs(i, i);
			break;
		}
	}
	for(int i = 0; i < m; i++) {
		int a;
		scanf("%d", &a);
		int mn = MAXN, mx = 0;
		for(int j = 0; j < a; j++) {
			int b;
			scanf("%d", &b);
			mn = min(mn, id[b]);
			mx = max(mx, id[b]);
		}
		update(1, 1, n, mn + 1, mx);
	}
	vector <int> v;
	for(int i = 2; i <= n; i++) {
		if(query(1, 1, n, i) >= k) v.push_back(mp[make_pair(inv[i - 1], inv[i])]);
	}
	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: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 'int main()':
railway.cpp:67: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:69: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:38: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:41: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:53:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a);
   ~~~~~^~~~~~~~~~
railway.cpp:57:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &b);
    ~~~~~^~~~~~~~~~

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