Submission #864484

#	Time	Username	Problem	Language	Result	Execution time	Memory
864484		maks007	Railway (BOI17_railway)	C++14	0 / 100	1096 ms	31600 KiB

railway

#include "bits/stdc++.h"

using namespace std;

vector <vector <int>> g;
map <pair <int,int>,int> mp, edge, path;
int f;

void dfs(int v, const int target, int p = -1) {
	if(p != -1) path[{min(v, p), max(v, p)}] ++;
	if(v == target) {
		f = 1;
		return;
	}
	for(auto u : g[v]) {
		if(u == p) continue;
		dfs(u, target, v);
		if(f) return;
	}
	if(p != -1 && !f)
		path[{min(v, p), max(v, p)}] --;
}

signed main () {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, m, k;
	cin >> n >> m >> k;
	g.resize(n);
	for(int i = 0; i < n - 1; i ++) {
		int u, v;
		cin >> u >> v;
		u --, v --;
		edge[{min(u, v), max(u, v)}] = i + 1;
		g[u].push_back(v);
		g[v].push_back(u);		
	}
	for(int i = 0; i < m; i ++) {
		int sz;
		cin >> sz;
		int prev;
		cin >> prev;
		prev --;
		for(int j = 0; j < sz - 1; j ++) {
			int v;
			cin >> v;
			v --;
			f = 0;
			dfs(v, prev);
			prev = v;
		}
		for(auto &j : path) mp[j.first] += (j.second > 0), j.second = 0;
	}	
	vector <pair <int,int>> proof;
	for(auto i : mp) {
		if(i.second >= k) proof.push_back(i.first);
	}
	cout << proof.size() << "\n";
	for(auto i : proof) {
		cout << edge[i] << " ";
	}
	return 0;
}

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