Submission #145156

#	Time	Username	Problem	Language	Result	Execution time	Memory
145156		tincamatei	Railway (BOI17_railway)	C++14	100 / 100	170 ms	26024 KiB

railway

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100000;
const int MAX_K = 50000;

vector<int> graph[1+MAX_N];
vector<int> updates[1+MAX_N];
int lim[MAX_K], subtree[1+MAX_N];

struct SubTreeCnt {
	int cnt[MAX_K];
	int active;
	vector<int> history;

	SubTreeCnt() {
		for(int i = 0; i < MAX_K; ++i)
			cnt[i] = 0;
		active = 0;
	}

	void clear() {
		for(auto it: history)
			cnt[it]--;
		active = 0;
		history.clear();
	}

	void insert(int x) {
		if(cnt[x] == 0)
			++active;
		if(cnt[x] == lim[x] - 1)
			--active;
		cnt[x]++;

		history.push_back(x);
	}

	int getActive() {
		return active;
	}
} freq;

struct Edge {
	int a, b;
	int cnt;
	int other(int x) {
		return a ^ b ^ x;
	}
} edges[MAX_N - 1];

void predfs(int nod, int fatherEdge = -1) {
	subtree[nod] = 1;
	for(auto it: graph[nod]) {
		int son = edges[it].other(nod);
		if(it != fatherEdge) {
			predfs(son, it);
			subtree[nod] += subtree[son];
		}
	}
}

void updateDfs(int nod, int fatherEdge = -1) {
	for(auto it: updates[nod])
		freq.insert(it);
	
	for(auto it: graph[nod]) {
		int son = edges[it].other(nod);
		if(it != fatherEdge)
			updateDfs(son, it);
	}
}

void dfs(int nod, int fatherEdge = -1) {
	int heavyson = -1, heavyedge = -1;
	for(auto it: graph[nod]) {
		int son = edges[it].other(nod);
		if(it != fatherEdge && (heavyson == -1 || (heavyson != -1 && subtree[son] > subtree[heavyson]))) {
			heavyson = son;
			heavyedge = it;
		}
	}

	for(auto it: graph[nod]) {
		int son = edges[it].other(nod);
		if(it != fatherEdge && son != heavyson) {
			dfs(son, it);
			edges[it].cnt = freq.getActive();
			freq.clear();
		}
	}

	if(heavyson != -1) {
		dfs(heavyson, heavyedge);
		edges[heavyedge].cnt = freq.getActive();
		for(auto it: graph[nod]) {
			int son = edges[it].other(nod);
			if(it != fatherEdge && son != heavyson)
				updateDfs(son, it);
		}
	}

	for(auto it: updates[nod])
		freq.insert(it);
}

int main() {
	int n, m, k, a, b, s, nr;

	scanf("%d%d%d", &n, &m, &k);
	for(int i = 0; i < n - 1; ++i) {
		scanf("%d%d", &a, &b);
		edges[i].a = a;
		edges[i].b = b;
		graph[a].push_back(i);
		graph[b].push_back(i);
	}
	for(int i = 0; i < m; ++i) {
		scanf("%d", &s);
		for(int j = 0; j < s; ++j) {
			scanf("%d", &a);
			updates[a].push_back(i);
		}
		lim[i] = s;
	}

	predfs(1);
	dfs(1);

	nr = 0;
	for(int i = 0; i < n - 1; ++i)
		if(edges[i].cnt >= k)
			++nr;
	
	printf("%d\n", nr);
	for(int i = 0; i < n - 1; ++i)
		if(edges[i].cnt >= k)
			printf("%d ", i + 1);

	return 0;
}

Compilation message (stderr)

railway.cpp: In function 'int main()':
railway.cpp:111: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:113: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:120:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &s);
   ~~~~~^~~~~~~~~~
railway.cpp:122:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &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