oj.uz

답안 #757738

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
757738 2023-06-13T17:08:57 Z SteGG Railway (BOI17_railway) C++17
100 / 100
 155 ms 43652 KB 
//Judges with GCC >= 12 only needs Ofast
//#pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
//MLE optimization
//#pragma GCC optimize("conserve-stack")
//Old judges
//#pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2")
//New judges. Test with assert(__builtin_cpu_supports("avx2"));
//#pragma GCC target("arch=skylake")
//Atcoder
//#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
//using namespace __gnu_pbds;

//template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

//write variables and debug
#define bugf cout << "Here" << endl
#define bug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#define bugarr(arr,...) cout << #arr; _dbg_arr(arr, __VA_ARGS__)

template <class T>
ostream& operator<<(ostream& output, const vector<T> &arr){
	int n = arr.size();
	output << "[";
	for(int i = 0; i < n; i++){
		output << arr[i];
		if(i != n - 1) output << ", ";
	}
	output << "]";
	return output;
}

template<class T, class U>
ostream& operator<<(ostream& output, const pair<T, U> &A){
	output << "(" << A.first << ", " << A.second <<  ")";
	return output;
}

template<class T>
ostream& operator<<(ostream& output, const set<T> &s){
	output << "{";
	for(auto it = s.begin(); it != s.end(); it++){
		if(it != s.begin()) output << ", ";
		output << (*it);
	}
	output << "}";
	return output;
}

template<class T, class U>
ostream& operator<<(ostream& output, const map<T, U> &m){
	output << "{";
	for(auto it = m.begin(); it != m.end(); it++){
		if(it != m.begin()) output << ", ";
		output << "(" << it->first << " : " << it->second << ")";
	}
	output << "}";
	return output;
}

template<class TH>
void _dbg(const char *sdbg, TH h){
	cout << sdbg << " = " << h << endl;
}

template<class TH, class... TA>
void _dbg(const char *sdbg, TH h, TA... a) {
	while(*sdbg != ',')cout << *sdbg++;
	cout << " = " << h << "\n";
	_dbg(sdbg+1, a...);
}

template<class _Arr, class _Index>
void _dbg_arr(_Arr arr, _Index index){
	cout << '[' << index << "] = " << arr[index] << endl;
}

template<class _Arr, class _Index, class... TA>
void _dbg_arr(_Arr &arr, _Index index, TA... args){
	cout << '[' << index << ']';
	_dbg_arr(arr[index], args...);
}

//open file
#define taskname "" //name input and output file

#ifdef SteGG
void open(){
	if(fopen("input.inp", "r")){
		freopen("input.inp", "r", stdin);
		freopen("output.out", "w", stdout);
	}
}
#else
void open(){
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
		freopen(taskname".out", "w", stdout);
	}
}
#endif

//initialize
#define testcase \
	long long test; \
	cin >> test; \
	for(int tst = 1; tst <= test; tst++)
#define int long long
#define MOD 1000000007
#define FFTMOD (119 << 23 | 1)
#define EPSILON 1e-9
#define setpre(x) fixed << setprecision(x)
#define cd complex<double>
#define all(x) x.begin(), x.end()
#define endl '\n'

const long long INF = 3e18L + 5;
const int inf = 1e9 + 7;
const double infd = 1e60;
const double PI = acos(-1);
const int maxn = 1e5 + 5;
//const int base = ;
int n, m, k;
vector<int> id_edges[maxn];
int sz_query[maxn];
vector<int> id_query[maxn];
unordered_map<int, int> *sus[maxn];
int finished[maxn];
vector<int> result;

//others struct or class

struct Edge{
	int u, v;
	Edge() : u(0), v(0) {}
	Edge(int _u, int _v) : u(_u), v(_v) {}
	int get(int _u){
		if(_u == u) return v;
		else return u;
	}
};

//others function

//others init

Edge edges[maxn];

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	open();
	cin >> n >> m >> k;
	for(int i = 1; i < n; i++){
		int u, v;
		cin >> u >> v;
		edges[i] = Edge(u, v);
		id_edges[u].push_back(i);
		id_edges[v].push_back(i);
	}

	for(int i = 1; i <= m; i++){
		int sz;
		cin >> sz;
		sz_query[i] = sz;
		for(int j = 1; j <= sz; j++){
			int u;
			cin >> u;
			id_query[u].push_back(i);
		}
	}	

	function<int(int, int, int)> dfs = [&](int u, int p, int cur_id) -> int {
		int sz_subtree = 1;
		vector<int> children;
		int largest = -1;
		int max_sz = 0;
		for(int id : id_edges[u]){
			int v = edges[id].get(u);
			if(v == p) continue;
			children.push_back(v);
			int temp = dfs(v, u, id);
			if(largest == -1 || max_sz < temp){
				max_sz = temp;
				largest = v;
			}
			sz_subtree += temp;
		}

		if(largest == -1){
			sus[u] = new unordered_map<int, int>();
			finished[u] = 0;
		}else{
			sus[u] = sus[largest];
			finished[u] = finished[largest];
		}


		for(int child : children){
			if(child == largest) continue;
			for(auto it = sus[child]->begin(); it != sus[child]->end(); it++){
				int id_q = it->first;
				int cnt = it->second;
				(*sus[u])[id_q] += cnt;
				if((*sus[u])[id_q] == sz_query[id_q]) finished[u]++;
			}
		}

		for(int id_q : id_query[u]){
			(*sus[u])[id_q]++;
			if((*sus[u])[id_q] == sz_query[id_q]) finished[u]++;
		}

		if(sus[u]->size() - finished[u] >= k) result.push_back(cur_id);
		return sz_subtree;
	};

	dfs(1, 0, -1);

	sort(all(result));

	cout << result.size() << endl;
	for(int i = 0; i < result.size(); i++){
		cout << result[i];
		if(i != result.size() - 1) cout << " ";
		else cout << endl;
	}

	return 0;
}

Compilation message

railway.cpp: In lambda function:
railway.cpp:219:35: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'long long int' [-Wsign-compare]
  219 |   if(sus[u]->size() - finished[u] >= k) result.push_back(cur_id);
      |      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
railway.cpp: In function 'int main()':
railway.cpp:228:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  228 |  for(int i = 0; i < result.size(); i++){
      |                 ~~^~~~~~~~~~~~~~~
railway.cpp:230:8: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  230 |   if(i != result.size() - 1) cout << " ";
      |      ~~^~~~~~~~~~~~~~~~~~~~
railway.cpp: In function 'void open()':
railway.cpp:101:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |   freopen(taskname".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
railway.cpp:102:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |   freopen(taskname".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 6612 KB Output is correct
2 Correct 8 ms 7636 KB Output is correct
3 Correct 8 ms 7636 KB Output is correct
4 Correct 4 ms 6620 KB Output is correct
5 Correct 4 ms 6484 KB Output is correct
6 Correct 9 ms 8660 KB Output is correct
7 Correct 12 ms 7988 KB Output is correct
8 Correct 8 ms 8276 KB Output is correct
9 Correct 9 ms 8276 KB Output is correct
10 Correct 4 ms 6608 KB Output is correct
11 Correct 5 ms 6600 KB Output is correct
12 Correct 4 ms 6612 KB Output is correct
13 Correct 3 ms 6484 KB Output is correct
14 Correct 4 ms 6612 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 6612 KB Output is correct
2 Correct 8 ms 7636 KB Output is correct
3 Correct 8 ms 7636 KB Output is correct
4 Correct 4 ms 6620 KB Output is correct
5 Correct 4 ms 6484 KB Output is correct
6 Correct 9 ms 8660 KB Output is correct
7 Correct 12 ms 7988 KB Output is correct
8 Correct 8 ms 8276 KB Output is correct
9 Correct 9 ms 8276 KB Output is correct
10 Correct 4 ms 6608 KB Output is correct
11 Correct 5 ms 6600 KB Output is correct
12 Correct 4 ms 6612 KB Output is correct
13 Correct 3 ms 6484 KB Output is correct
14 Correct 4 ms 6612 KB Output is correct
15 Correct 25 ms 12148 KB Output is correct
16 Correct 26 ms 12236 KB Output is correct
17 Correct 31 ms 12260 KB Output is correct
18 Correct 10 ms 8668 KB Output is correct
19 Correct 9 ms 8024 KB Output is correct
20 Correct 32 ms 14080 KB Output is correct
21 Correct 27 ms 14036 KB Output is correct
22 Correct 4 ms 6612 KB Output is correct
23 Correct 9 ms 7636 KB Output is correct
24 Correct 7 ms 7640 KB Output is correct
25 Correct 3 ms 6592 KB Output is correct
26 Correct 3 ms 6612 KB Output is correct
27 Correct 8 ms 8660 KB Output is correct
28 Correct 8 ms 7900 KB Output is correct
29 Correct 7 ms 8284 KB Output is correct
30 Correct 8 ms 8152 KB Output is correct
31 Correct 4 ms 6604 KB Output is correct
32 Correct 3 ms 6608 KB Output is correct
33 Correct 4 ms 6600 KB Output is correct
34 Correct 4 ms 6604 KB Output is correct
35 Correct 3 ms 6604 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 88 ms 38500 KB Output is correct
2 Correct 3 ms 6600 KB Output is correct
3 Correct 85 ms 38048 KB Output is correct
4 Correct 79 ms 37424 KB Output is correct
5 Correct 78 ms 37064 KB Output is correct
6 Correct 71 ms 37320 KB Output is correct

Subtask #4
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 73 ms 29988 KB Output is correct
2 Correct 94 ms 27232 KB Output is correct
3 Correct 115 ms 32336 KB Output is correct
4 Correct 122 ms 37836 KB Output is correct
5 Correct 119 ms 34896 KB Output is correct
6 Correct 81 ms 30064 KB Output is correct
7 Correct 68 ms 29884 KB Output is correct

Subtask #5
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 73 ms 29988 KB Output is correct
2 Correct 94 ms 27232 KB Output is correct
3 Correct 115 ms 32336 KB Output is correct
4 Correct 122 ms 37836 KB Output is correct
5 Correct 119 ms 34896 KB Output is correct
6 Correct 81 ms 30064 KB Output is correct
7 Correct 68 ms 29884 KB Output is correct
8 Correct 88 ms 31748 KB Output is correct
9 Correct 89 ms 31540 KB Output is correct
10 Correct 81 ms 37680 KB Output is correct
11 Correct 82 ms 37476 KB Output is correct
12 Correct 89 ms 31716 KB Output is correct
13 Correct 83 ms 31848 KB Output is correct
14 Correct 100 ms 28548 KB Output is correct
15 Correct 98 ms 27840 KB Output is correct
16 Correct 118 ms 38236 KB Output is correct
17 Correct 117 ms 38872 KB Output is correct
18 Correct 121 ms 36680 KB Output is correct
19 Correct 94 ms 26920 KB Output is correct
20 Correct 82 ms 30792 KB Output is correct
21 Correct 74 ms 30920 KB Output is correct
22 Correct 91 ms 31084 KB Output is correct

Subtask #6
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 6612 KB Output is correct
2 Correct 8 ms 7636 KB Output is correct
3 Correct 8 ms 7636 KB Output is correct
4 Correct 4 ms 6620 KB Output is correct
5 Correct 4 ms 6484 KB Output is correct
6 Correct 9 ms 8660 KB Output is correct
7 Correct 12 ms 7988 KB Output is correct
8 Correct 8 ms 8276 KB Output is correct
9 Correct 9 ms 8276 KB Output is correct
10 Correct 4 ms 6608 KB Output is correct
11 Correct 5 ms 6600 KB Output is correct
12 Correct 4 ms 6612 KB Output is correct
13 Correct 3 ms 6484 KB Output is correct
14 Correct 4 ms 6612 KB Output is correct
15 Correct 25 ms 12148 KB Output is correct
16 Correct 26 ms 12236 KB Output is correct
17 Correct 31 ms 12260 KB Output is correct
18 Correct 10 ms 8668 KB Output is correct
19 Correct 9 ms 8024 KB Output is correct
20 Correct 32 ms 14080 KB Output is correct
21 Correct 27 ms 14036 KB Output is correct
22 Correct 4 ms 6612 KB Output is correct
23 Correct 9 ms 7636 KB Output is correct
24 Correct 7 ms 7640 KB Output is correct
25 Correct 3 ms 6592 KB Output is correct
26 Correct 3 ms 6612 KB Output is correct
27 Correct 8 ms 8660 KB Output is correct
28 Correct 8 ms 7900 KB Output is correct
29 Correct 7 ms 8284 KB Output is correct
30 Correct 8 ms 8152 KB Output is correct
31 Correct 4 ms 6604 KB Output is correct
32 Correct 3 ms 6608 KB Output is correct
33 Correct 4 ms 6600 KB Output is correct
34 Correct 4 ms 6604 KB Output is correct
35 Correct 3 ms 6604 KB Output is correct
36 Correct 88 ms 38500 KB Output is correct
37 Correct 3 ms 6600 KB Output is correct
38 Correct 85 ms 38048 KB Output is correct
39 Correct 79 ms 37424 KB Output is correct
40 Correct 78 ms 37064 KB Output is correct
41 Correct 71 ms 37320 KB Output is correct
42 Correct 73 ms 29988 KB Output is correct
43 Correct 94 ms 27232 KB Output is correct
44 Correct 115 ms 32336 KB Output is correct
45 Correct 122 ms 37836 KB Output is correct
46 Correct 119 ms 34896 KB Output is correct
47 Correct 81 ms 30064 KB Output is correct
48 Correct 68 ms 29884 KB Output is correct
49 Correct 88 ms 31748 KB Output is correct
50 Correct 89 ms 31540 KB Output is correct
51 Correct 81 ms 37680 KB Output is correct
52 Correct 82 ms 37476 KB Output is correct
53 Correct 89 ms 31716 KB Output is correct
54 Correct 83 ms 31848 KB Output is correct
55 Correct 100 ms 28548 KB Output is correct
56 Correct 98 ms 27840 KB Output is correct
57 Correct 118 ms 38236 KB Output is correct
58 Correct 117 ms 38872 KB Output is correct
59 Correct 121 ms 36680 KB Output is correct
60 Correct 94 ms 26920 KB Output is correct
61 Correct 82 ms 30792 KB Output is correct
62 Correct 74 ms 30920 KB Output is correct
63 Correct 91 ms 31084 KB Output is correct
64 Correct 89 ms 32520 KB Output is correct
65 Correct 155 ms 41444 KB Output is correct
66 Correct 129 ms 36044 KB Output is correct
67 Correct 117 ms 31604 KB Output is correct
68 Correct 73 ms 28024 KB Output is correct
69 Correct 103 ms 28024 KB Output is correct
70 Correct 97 ms 33924 KB Output is correct
71 Correct 90 ms 31900 KB Output is correct
72 Correct 4 ms 6612 KB Output is correct
73 Correct 8 ms 7696 KB Output is correct
74 Correct 7 ms 7624 KB Output is correct
75 Correct 4 ms 6484 KB Output is correct
76 Correct 4 ms 6484 KB Output is correct
77 Correct 9 ms 8664 KB Output is correct
78 Correct 8 ms 7896 KB Output is correct
79 Correct 8 ms 8276 KB Output is correct
80 Correct 9 ms 8276 KB Output is correct
81 Correct 4 ms 6484 KB Output is correct
82 Correct 4 ms 6600 KB Output is correct
83 Correct 4 ms 6608 KB Output is correct
84 Correct 5 ms 6612 KB Output is correct
85 Correct 4 ms 6612 KB Output is correct
86 Correct 27 ms 12252 KB Output is correct
87 Correct 29 ms 12272 KB Output is correct
88 Correct 36 ms 12348 KB Output is correct
89 Correct 8 ms 8660 KB Output is correct
90 Correct 10 ms 8020 KB Output is correct
91 Correct 35 ms 14108 KB Output is correct
92 Correct 38 ms 14020 KB Output is correct
93 Correct 4 ms 6604 KB Output is correct
94 Correct 81 ms 39028 KB Output is correct
95 Correct 80 ms 38648 KB Output is correct
96 Correct 77 ms 38000 KB Output is correct
97 Correct 75 ms 37568 KB Output is correct
98 Correct 79 ms 37828 KB Output is correct
99 Correct 132 ms 36864 KB Output is correct
100 Correct 133 ms 36676 KB Output is correct
101 Correct 132 ms 43652 KB Output is correct
102 Correct 98 ms 28044 KB Output is correct
103 Correct 96 ms 30544 KB Output is correct
104 Correct 77 ms 31108 KB Output is correct
105 Correct 73 ms 30496 KB Output is correct
106 Correct 94 ms 32120 KB Output is correct
107 Correct 89 ms 32020 KB Output is correct
108 Correct 80 ms 38060 KB Output is correct
109 Correct 73 ms 37368 KB Output is correct
110 Correct 77 ms 31992 KB Output is correct
111 Correct 81 ms 31996 KB Output is correct
112 Correct 105 ms 28736 KB Output is correct
113 Correct 98 ms 28132 KB Output is correct