Submission #145151

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
145151	2019-08-18T22:37:42 Z	tincamatei	Railway (BOI17_railway)	C++14	7 / 100	500 ms	524292 KB

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(nod, 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

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
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	438 ms	524288 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	438 ms	524288 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #3
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	103 ms	23668 KB	Output is correct
2	Correct	6 ms	5240 KB	Output is correct
3	Correct	101 ms	23504 KB	Output is correct
4	Correct	100 ms	23392 KB	Output is correct
5	Correct	101 ms	23540 KB	Output is correct
6	Correct	98 ms	23664 KB	Output is correct