# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
942947 |
2024-03-11T07:17:42 Z |
Baizho |
Railway (BOI17_railway) |
C++14 |
|
308 ms |
53184 KB |
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>
// #pragma GCC optimize("Ofast,unroll-loops,fast-math")
// #pragma GCC target("popcnt,sse3,avx")
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> pll;
#define sz size()
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define pb push_back
const int mod = ll(1e9)+7; //(b + (a%b)) % b (to mod -1%(10^9+7) correctly in c++ its -1 but its suppose to be 10^9+6
const ll MOD = 998244353; // (a%mod)*(binpow(b,mod-2,mod) = (a/b)%mod
const int N = ll(1e5)+100;
const int M = ll(2e5) + 100;
const long long inf = 5e18;
//const long double eps = 1e-15L;
ll lcm(ll a, ll b) { return (a / __gcd(a,b))*b; }
ll binpow(ll a, ll b, ll m) { ll res=1; a %= m; while(b>0){ if(b&1)res=(res * a) % m; a=(a * a) % m; b/=2; } return res%m;}
void Freopen(string Key){ freopen((Key+".in").c_str(), "r", stdin); freopen((Key+".out").c_str(), "w", stdout); }
int n, m, k, a[N], b[N], cnt[N], siz[N];
map<pair<int, int>, int> id;
map<int, int> mp[N];
vector<int> g[N], que[N];
void dfs(int v, int p = 0) {
for(auto i : que[v]) {
mp[v][i] ++;
if(mp[v][i] == siz[i]) mp[v].erase(i);
}
for(auto to : g[v]) {
if(to == p) continue;
dfs(to, v);
cnt[id[{v, to}]] += mp[to].size();
if(mp[v].size() < mp[to].size()) swap(mp[v], mp[to]);
for(auto x : mp[to]) {
mp[v][x.ff] += x.ss;
if(mp[v][x.ff] == siz[x.ff]) mp[v].erase(x.ff);
}
}
}
void Baizho() {
cin>>n>>m>>k;
for(int i = 1; i <= n - 1; i ++) {
cin>>a[i]>>b[i];
id[{a[i], b[i]}] = id[{b[i], a[i]}] = i;
g[a[i]].pb(b[i]);
g[b[i]].pb(a[i]);
}
for(int i = 1; i <= m; i ++) {
cin>>siz[i];
for(int j = 1; j <= siz[i]; j ++) {
int si; cin>>si;
que[si].pb(i);
}
}
dfs(1);
vector<int> ans;
for(int i = 1; i <= n; i ++) {
if(cnt[i] >= k) ans.pb(i);
}
cout<<ans.size()<<"\n";
for(auto x : ans) cout<<x<<" ";
}
signed main() {
// Freopen("nondec");
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
// precalc();
int ttt = 1;
// cin>>ttt;
for(int i=1; i<=ttt; i++) {Baizho(); }
}
Compilation message
railway.cpp: In function 'void Freopen(std::string)':
railway.cpp:35:34: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
35 | void Freopen(string Key){ freopen((Key+".in").c_str(), "r", stdin); freopen((Key+".out").c_str(), "w", stdout); }
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
railway.cpp:35:76: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
35 | void Freopen(string Key){ freopen((Key+".in").c_str(), "r", stdin); freopen((Key+".out").c_str(), "w", stdout); }
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
10844 KB |
Output is correct |
2 |
Correct |
11 ms |
12636 KB |
Output is correct |
3 |
Correct |
10 ms |
12636 KB |
Output is correct |
4 |
Correct |
2 ms |
10844 KB |
Output is correct |
5 |
Correct |
2 ms |
10844 KB |
Output is correct |
6 |
Correct |
10 ms |
13500 KB |
Output is correct |
7 |
Correct |
9 ms |
12892 KB |
Output is correct |
8 |
Correct |
10 ms |
12780 KB |
Output is correct |
9 |
Correct |
9 ms |
12888 KB |
Output is correct |
10 |
Correct |
2 ms |
10840 KB |
Output is correct |
11 |
Correct |
3 ms |
10844 KB |
Output is correct |
12 |
Correct |
3 ms |
10844 KB |
Output is correct |
13 |
Correct |
4 ms |
11100 KB |
Output is correct |
14 |
Correct |
2 ms |
10844 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
10844 KB |
Output is correct |
2 |
Correct |
11 ms |
12636 KB |
Output is correct |
3 |
Correct |
10 ms |
12636 KB |
Output is correct |
4 |
Correct |
2 ms |
10844 KB |
Output is correct |
5 |
Correct |
2 ms |
10844 KB |
Output is correct |
6 |
Correct |
10 ms |
13500 KB |
Output is correct |
7 |
Correct |
9 ms |
12892 KB |
Output is correct |
8 |
Correct |
10 ms |
12780 KB |
Output is correct |
9 |
Correct |
9 ms |
12888 KB |
Output is correct |
10 |
Correct |
2 ms |
10840 KB |
Output is correct |
11 |
Correct |
3 ms |
10844 KB |
Output is correct |
12 |
Correct |
3 ms |
10844 KB |
Output is correct |
13 |
Correct |
4 ms |
11100 KB |
Output is correct |
14 |
Correct |
2 ms |
10844 KB |
Output is correct |
15 |
Correct |
41 ms |
19028 KB |
Output is correct |
16 |
Correct |
37 ms |
18952 KB |
Output is correct |
17 |
Correct |
38 ms |
19284 KB |
Output is correct |
18 |
Correct |
10 ms |
13400 KB |
Output is correct |
19 |
Correct |
12 ms |
12732 KB |
Output is correct |
20 |
Correct |
37 ms |
18560 KB |
Output is correct |
21 |
Correct |
38 ms |
18512 KB |
Output is correct |
22 |
Correct |
2 ms |
10844 KB |
Output is correct |
23 |
Correct |
12 ms |
12560 KB |
Output is correct |
24 |
Correct |
10 ms |
12632 KB |
Output is correct |
25 |
Correct |
2 ms |
10840 KB |
Output is correct |
26 |
Correct |
2 ms |
10844 KB |
Output is correct |
27 |
Correct |
9 ms |
13404 KB |
Output is correct |
28 |
Correct |
10 ms |
12668 KB |
Output is correct |
29 |
Correct |
8 ms |
12636 KB |
Output is correct |
30 |
Correct |
9 ms |
12892 KB |
Output is correct |
31 |
Correct |
2 ms |
10892 KB |
Output is correct |
32 |
Correct |
2 ms |
10896 KB |
Output is correct |
33 |
Correct |
2 ms |
10844 KB |
Output is correct |
34 |
Correct |
2 ms |
10844 KB |
Output is correct |
35 |
Correct |
2 ms |
10680 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
144 ms |
51540 KB |
Output is correct |
2 |
Correct |
3 ms |
10844 KB |
Output is correct |
3 |
Correct |
140 ms |
51092 KB |
Output is correct |
4 |
Correct |
136 ms |
50596 KB |
Output is correct |
5 |
Correct |
122 ms |
50700 KB |
Output is correct |
6 |
Correct |
128 ms |
53184 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
151 ms |
42840 KB |
Output is correct |
2 |
Correct |
189 ms |
38256 KB |
Output is correct |
3 |
Correct |
228 ms |
44320 KB |
Output is correct |
4 |
Correct |
226 ms |
44980 KB |
Output is correct |
5 |
Correct |
229 ms |
44376 KB |
Output is correct |
6 |
Correct |
155 ms |
42976 KB |
Output is correct |
7 |
Correct |
160 ms |
43068 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
151 ms |
42840 KB |
Output is correct |
2 |
Correct |
189 ms |
38256 KB |
Output is correct |
3 |
Correct |
228 ms |
44320 KB |
Output is correct |
4 |
Correct |
226 ms |
44980 KB |
Output is correct |
5 |
Correct |
229 ms |
44376 KB |
Output is correct |
6 |
Correct |
155 ms |
42976 KB |
Output is correct |
7 |
Correct |
160 ms |
43068 KB |
Output is correct |
8 |
Correct |
148 ms |
42832 KB |
Output is correct |
9 |
Correct |
157 ms |
42556 KB |
Output is correct |
10 |
Correct |
130 ms |
50364 KB |
Output is correct |
11 |
Correct |
123 ms |
50376 KB |
Output is correct |
12 |
Correct |
107 ms |
35552 KB |
Output is correct |
13 |
Correct |
136 ms |
35524 KB |
Output is correct |
14 |
Correct |
189 ms |
40020 KB |
Output is correct |
15 |
Correct |
193 ms |
40300 KB |
Output is correct |
16 |
Correct |
210 ms |
45832 KB |
Output is correct |
17 |
Correct |
204 ms |
46424 KB |
Output is correct |
18 |
Correct |
208 ms |
44084 KB |
Output is correct |
19 |
Correct |
199 ms |
39252 KB |
Output is correct |
20 |
Correct |
158 ms |
43348 KB |
Output is correct |
21 |
Correct |
154 ms |
43476 KB |
Output is correct |
22 |
Correct |
150 ms |
43096 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
10844 KB |
Output is correct |
2 |
Correct |
11 ms |
12636 KB |
Output is correct |
3 |
Correct |
10 ms |
12636 KB |
Output is correct |
4 |
Correct |
2 ms |
10844 KB |
Output is correct |
5 |
Correct |
2 ms |
10844 KB |
Output is correct |
6 |
Correct |
10 ms |
13500 KB |
Output is correct |
7 |
Correct |
9 ms |
12892 KB |
Output is correct |
8 |
Correct |
10 ms |
12780 KB |
Output is correct |
9 |
Correct |
9 ms |
12888 KB |
Output is correct |
10 |
Correct |
2 ms |
10840 KB |
Output is correct |
11 |
Correct |
3 ms |
10844 KB |
Output is correct |
12 |
Correct |
3 ms |
10844 KB |
Output is correct |
13 |
Correct |
4 ms |
11100 KB |
Output is correct |
14 |
Correct |
2 ms |
10844 KB |
Output is correct |
15 |
Correct |
41 ms |
19028 KB |
Output is correct |
16 |
Correct |
37 ms |
18952 KB |
Output is correct |
17 |
Correct |
38 ms |
19284 KB |
Output is correct |
18 |
Correct |
10 ms |
13400 KB |
Output is correct |
19 |
Correct |
12 ms |
12732 KB |
Output is correct |
20 |
Correct |
37 ms |
18560 KB |
Output is correct |
21 |
Correct |
38 ms |
18512 KB |
Output is correct |
22 |
Correct |
2 ms |
10844 KB |
Output is correct |
23 |
Correct |
12 ms |
12560 KB |
Output is correct |
24 |
Correct |
10 ms |
12632 KB |
Output is correct |
25 |
Correct |
2 ms |
10840 KB |
Output is correct |
26 |
Correct |
2 ms |
10844 KB |
Output is correct |
27 |
Correct |
9 ms |
13404 KB |
Output is correct |
28 |
Correct |
10 ms |
12668 KB |
Output is correct |
29 |
Correct |
8 ms |
12636 KB |
Output is correct |
30 |
Correct |
9 ms |
12892 KB |
Output is correct |
31 |
Correct |
2 ms |
10892 KB |
Output is correct |
32 |
Correct |
2 ms |
10896 KB |
Output is correct |
33 |
Correct |
2 ms |
10844 KB |
Output is correct |
34 |
Correct |
2 ms |
10844 KB |
Output is correct |
35 |
Correct |
2 ms |
10680 KB |
Output is correct |
36 |
Correct |
144 ms |
51540 KB |
Output is correct |
37 |
Correct |
3 ms |
10844 KB |
Output is correct |
38 |
Correct |
140 ms |
51092 KB |
Output is correct |
39 |
Correct |
136 ms |
50596 KB |
Output is correct |
40 |
Correct |
122 ms |
50700 KB |
Output is correct |
41 |
Correct |
128 ms |
53184 KB |
Output is correct |
42 |
Correct |
151 ms |
42840 KB |
Output is correct |
43 |
Correct |
189 ms |
38256 KB |
Output is correct |
44 |
Correct |
228 ms |
44320 KB |
Output is correct |
45 |
Correct |
226 ms |
44980 KB |
Output is correct |
46 |
Correct |
229 ms |
44376 KB |
Output is correct |
47 |
Correct |
155 ms |
42976 KB |
Output is correct |
48 |
Correct |
160 ms |
43068 KB |
Output is correct |
49 |
Correct |
148 ms |
42832 KB |
Output is correct |
50 |
Correct |
157 ms |
42556 KB |
Output is correct |
51 |
Correct |
130 ms |
50364 KB |
Output is correct |
52 |
Correct |
123 ms |
50376 KB |
Output is correct |
53 |
Correct |
107 ms |
35552 KB |
Output is correct |
54 |
Correct |
136 ms |
35524 KB |
Output is correct |
55 |
Correct |
189 ms |
40020 KB |
Output is correct |
56 |
Correct |
193 ms |
40300 KB |
Output is correct |
57 |
Correct |
210 ms |
45832 KB |
Output is correct |
58 |
Correct |
204 ms |
46424 KB |
Output is correct |
59 |
Correct |
208 ms |
44084 KB |
Output is correct |
60 |
Correct |
199 ms |
39252 KB |
Output is correct |
61 |
Correct |
158 ms |
43348 KB |
Output is correct |
62 |
Correct |
154 ms |
43476 KB |
Output is correct |
63 |
Correct |
150 ms |
43096 KB |
Output is correct |
64 |
Correct |
182 ms |
42904 KB |
Output is correct |
65 |
Correct |
308 ms |
51936 KB |
Output is correct |
66 |
Correct |
238 ms |
48468 KB |
Output is correct |
67 |
Correct |
207 ms |
43732 KB |
Output is correct |
68 |
Correct |
130 ms |
33480 KB |
Output is correct |
69 |
Correct |
110 ms |
33188 KB |
Output is correct |
70 |
Correct |
151 ms |
44072 KB |
Output is correct |
71 |
Correct |
159 ms |
42792 KB |
Output is correct |
72 |
Correct |
2 ms |
10840 KB |
Output is correct |
73 |
Correct |
11 ms |
12632 KB |
Output is correct |
74 |
Correct |
10 ms |
12632 KB |
Output is correct |
75 |
Correct |
2 ms |
10844 KB |
Output is correct |
76 |
Correct |
2 ms |
10840 KB |
Output is correct |
77 |
Correct |
14 ms |
13404 KB |
Output is correct |
78 |
Correct |
11 ms |
13144 KB |
Output is correct |
79 |
Correct |
9 ms |
12636 KB |
Output is correct |
80 |
Correct |
14 ms |
12808 KB |
Output is correct |
81 |
Correct |
2 ms |
10844 KB |
Output is correct |
82 |
Correct |
3 ms |
10844 KB |
Output is correct |
83 |
Correct |
3 ms |
10904 KB |
Output is correct |
84 |
Correct |
3 ms |
10844 KB |
Output is correct |
85 |
Correct |
2 ms |
10844 KB |
Output is correct |
86 |
Correct |
39 ms |
18840 KB |
Output is correct |
87 |
Correct |
39 ms |
19092 KB |
Output is correct |
88 |
Correct |
38 ms |
19100 KB |
Output is correct |
89 |
Correct |
10 ms |
13404 KB |
Output is correct |
90 |
Correct |
10 ms |
12892 KB |
Output is correct |
91 |
Correct |
36 ms |
18516 KB |
Output is correct |
92 |
Correct |
37 ms |
18512 KB |
Output is correct |
93 |
Correct |
3 ms |
10844 KB |
Output is correct |
94 |
Correct |
142 ms |
51564 KB |
Output is correct |
95 |
Correct |
138 ms |
51080 KB |
Output is correct |
96 |
Correct |
139 ms |
50812 KB |
Output is correct |
97 |
Correct |
128 ms |
50412 KB |
Output is correct |
98 |
Correct |
130 ms |
53100 KB |
Output is correct |
99 |
Correct |
224 ms |
48720 KB |
Output is correct |
100 |
Correct |
207 ms |
45836 KB |
Output is correct |
101 |
Correct |
246 ms |
46032 KB |
Output is correct |
102 |
Correct |
199 ms |
38992 KB |
Output is correct |
103 |
Correct |
145 ms |
43080 KB |
Output is correct |
104 |
Correct |
168 ms |
43400 KB |
Output is correct |
105 |
Correct |
151 ms |
42832 KB |
Output is correct |
106 |
Correct |
141 ms |
43404 KB |
Output is correct |
107 |
Correct |
151 ms |
43088 KB |
Output is correct |
108 |
Correct |
114 ms |
50392 KB |
Output is correct |
109 |
Correct |
114 ms |
50400 KB |
Output is correct |
110 |
Correct |
100 ms |
35580 KB |
Output is correct |
111 |
Correct |
107 ms |
35472 KB |
Output is correct |
112 |
Correct |
190 ms |
40016 KB |
Output is correct |
113 |
Correct |
202 ms |
40232 KB |
Output is correct |