# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
527963 |
2022-02-18T20:54:39 Z |
jalsol |
Railway (BOI17_railway) |
C++11 |
|
173 ms |
34168 KB |
#ifdef LOCAL
#include "local_header.h"
#include "debugger.h"
#else
#include <bits/stdc++.h>
#define debug(...)
#define DB(...)
#endif // LOCAL
using namespace std;
#define Task ""
struct __Init__ {
__Init__() {
cin.tie(nullptr)->sync_with_stdio(false);
if (fopen(Task".inp", "r")) {
freopen(Task".inp", "r", stdin);
freopen(Task".out", "w", stdout); }
}
} __init__;
using ll = long long;
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define fi first
#define se second
#define For(i, l, r) for (int i = (l); i <= (r); ++i)
#define Ford(i, r, l) for (int i = (r); i >= (l); --i)
#define Rep(i, n) For (i, 0, (n) - 1)
#define Repd(i, n) Ford (i, (n) - 1, 0)
template<class C> int isz(const C& c) { return c.size(); }
template<class T> bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } return false; }
template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } return false; }
constexpr int eps = 1e-9;
constexpr int inf = 1e9;
constexpr ll linf = 1e18;
/// ============================================================================
constexpr int maxN = 1e5 + 5;
int n, m, k;
vector<pair<int, int>> g[maxN];
int s[maxN];
map<int, int> mp[maxN];
vector<int> ans;
void Dfs(int u, int p, int pid) {
for (const auto& e : g[u]) {
int v, id; tie(v, id) = e;
if (v == p) continue;
Dfs(v, u, id);
if (isz(mp[u]) < isz(mp[v])) {
mp[u].swap(mp[v]);
}
for (const auto& x : mp[v]) {
mp[u][x.fi] += x.se;
if (mp[u][x.fi] == s[x.fi]) mp[u].erase(x.fi);
}
}
if (isz(mp[u]) >= k) {
ans.push_back(pid);
}
}
signed main() {
cin >> n >> m >> k;
For (i, 1, n - 1) {
int u, v; cin >> u >> v;
g[u].emplace_back(v, i);
g[v].emplace_back(u, i);
}
For (i, 1, m) {
cin >> s[i];
Rep (_, s[i]) {
int u; cin >> u;
++mp[u][i];
}
}
ans.reserve(n);
Dfs(1, -1, -1);
cout << isz(ans) << '\n';
sort(all(ans));
for (int x : ans) cout << x << ' ';
}
/**
**/
Compilation message
railway.cpp: In constructor '__Init__::__Init__()':
railway.cpp:18:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
18 | freopen(Task".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
railway.cpp:19:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
19 | freopen(Task".out", "w", stdout); }
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7372 KB |
Output is correct |
2 |
Correct |
7 ms |
7900 KB |
Output is correct |
3 |
Correct |
7 ms |
7984 KB |
Output is correct |
4 |
Correct |
4 ms |
7248 KB |
Output is correct |
5 |
Correct |
4 ms |
7248 KB |
Output is correct |
6 |
Correct |
8 ms |
8616 KB |
Output is correct |
7 |
Correct |
7 ms |
8064 KB |
Output is correct |
8 |
Correct |
7 ms |
7972 KB |
Output is correct |
9 |
Correct |
7 ms |
8016 KB |
Output is correct |
10 |
Correct |
4 ms |
7376 KB |
Output is correct |
11 |
Correct |
4 ms |
7248 KB |
Output is correct |
12 |
Correct |
4 ms |
7248 KB |
Output is correct |
13 |
Correct |
4 ms |
7368 KB |
Output is correct |
14 |
Correct |
4 ms |
7376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7372 KB |
Output is correct |
2 |
Correct |
7 ms |
7900 KB |
Output is correct |
3 |
Correct |
7 ms |
7984 KB |
Output is correct |
4 |
Correct |
4 ms |
7248 KB |
Output is correct |
5 |
Correct |
4 ms |
7248 KB |
Output is correct |
6 |
Correct |
8 ms |
8616 KB |
Output is correct |
7 |
Correct |
7 ms |
8064 KB |
Output is correct |
8 |
Correct |
7 ms |
7972 KB |
Output is correct |
9 |
Correct |
7 ms |
8016 KB |
Output is correct |
10 |
Correct |
4 ms |
7376 KB |
Output is correct |
11 |
Correct |
4 ms |
7248 KB |
Output is correct |
12 |
Correct |
4 ms |
7248 KB |
Output is correct |
13 |
Correct |
4 ms |
7368 KB |
Output is correct |
14 |
Correct |
4 ms |
7376 KB |
Output is correct |
15 |
Correct |
39 ms |
13580 KB |
Output is correct |
16 |
Correct |
38 ms |
13704 KB |
Output is correct |
17 |
Correct |
38 ms |
13768 KB |
Output is correct |
18 |
Correct |
8 ms |
8656 KB |
Output is correct |
19 |
Correct |
8 ms |
8028 KB |
Output is correct |
20 |
Correct |
39 ms |
13064 KB |
Output is correct |
21 |
Correct |
40 ms |
13000 KB |
Output is correct |
22 |
Correct |
4 ms |
7312 KB |
Output is correct |
23 |
Correct |
7 ms |
7888 KB |
Output is correct |
24 |
Correct |
7 ms |
7888 KB |
Output is correct |
25 |
Correct |
4 ms |
7296 KB |
Output is correct |
26 |
Correct |
5 ms |
7248 KB |
Output is correct |
27 |
Correct |
8 ms |
8544 KB |
Output is correct |
28 |
Correct |
7 ms |
8024 KB |
Output is correct |
29 |
Correct |
6 ms |
8016 KB |
Output is correct |
30 |
Correct |
7 ms |
8024 KB |
Output is correct |
31 |
Correct |
4 ms |
7248 KB |
Output is correct |
32 |
Correct |
4 ms |
7376 KB |
Output is correct |
33 |
Correct |
4 ms |
7344 KB |
Output is correct |
34 |
Correct |
5 ms |
7376 KB |
Output is correct |
35 |
Correct |
4 ms |
7248 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
106 ms |
29820 KB |
Output is correct |
2 |
Correct |
4 ms |
7372 KB |
Output is correct |
3 |
Correct |
108 ms |
31252 KB |
Output is correct |
4 |
Correct |
104 ms |
30848 KB |
Output is correct |
5 |
Correct |
86 ms |
30504 KB |
Output is correct |
6 |
Correct |
96 ms |
33040 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
102 ms |
24692 KB |
Output is correct |
2 |
Correct |
126 ms |
22340 KB |
Output is correct |
3 |
Correct |
138 ms |
28036 KB |
Output is correct |
4 |
Correct |
139 ms |
28444 KB |
Output is correct |
5 |
Correct |
144 ms |
28104 KB |
Output is correct |
6 |
Correct |
116 ms |
26704 KB |
Output is correct |
7 |
Correct |
104 ms |
26604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
102 ms |
24692 KB |
Output is correct |
2 |
Correct |
126 ms |
22340 KB |
Output is correct |
3 |
Correct |
138 ms |
28036 KB |
Output is correct |
4 |
Correct |
139 ms |
28444 KB |
Output is correct |
5 |
Correct |
144 ms |
28104 KB |
Output is correct |
6 |
Correct |
116 ms |
26704 KB |
Output is correct |
7 |
Correct |
104 ms |
26604 KB |
Output is correct |
8 |
Correct |
89 ms |
25412 KB |
Output is correct |
9 |
Correct |
97 ms |
25296 KB |
Output is correct |
10 |
Correct |
74 ms |
30404 KB |
Output is correct |
11 |
Correct |
70 ms |
30276 KB |
Output is correct |
12 |
Correct |
61 ms |
17364 KB |
Output is correct |
13 |
Correct |
59 ms |
17372 KB |
Output is correct |
14 |
Correct |
112 ms |
23256 KB |
Output is correct |
15 |
Correct |
119 ms |
23576 KB |
Output is correct |
16 |
Correct |
143 ms |
29508 KB |
Output is correct |
17 |
Correct |
150 ms |
30192 KB |
Output is correct |
18 |
Correct |
133 ms |
27716 KB |
Output is correct |
19 |
Correct |
127 ms |
22876 KB |
Output is correct |
20 |
Correct |
108 ms |
26748 KB |
Output is correct |
21 |
Correct |
116 ms |
26796 KB |
Output is correct |
22 |
Correct |
108 ms |
26780 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7372 KB |
Output is correct |
2 |
Correct |
7 ms |
7900 KB |
Output is correct |
3 |
Correct |
7 ms |
7984 KB |
Output is correct |
4 |
Correct |
4 ms |
7248 KB |
Output is correct |
5 |
Correct |
4 ms |
7248 KB |
Output is correct |
6 |
Correct |
8 ms |
8616 KB |
Output is correct |
7 |
Correct |
7 ms |
8064 KB |
Output is correct |
8 |
Correct |
7 ms |
7972 KB |
Output is correct |
9 |
Correct |
7 ms |
8016 KB |
Output is correct |
10 |
Correct |
4 ms |
7376 KB |
Output is correct |
11 |
Correct |
4 ms |
7248 KB |
Output is correct |
12 |
Correct |
4 ms |
7248 KB |
Output is correct |
13 |
Correct |
4 ms |
7368 KB |
Output is correct |
14 |
Correct |
4 ms |
7376 KB |
Output is correct |
15 |
Correct |
39 ms |
13580 KB |
Output is correct |
16 |
Correct |
38 ms |
13704 KB |
Output is correct |
17 |
Correct |
38 ms |
13768 KB |
Output is correct |
18 |
Correct |
8 ms |
8656 KB |
Output is correct |
19 |
Correct |
8 ms |
8028 KB |
Output is correct |
20 |
Correct |
39 ms |
13064 KB |
Output is correct |
21 |
Correct |
40 ms |
13000 KB |
Output is correct |
22 |
Correct |
4 ms |
7312 KB |
Output is correct |
23 |
Correct |
7 ms |
7888 KB |
Output is correct |
24 |
Correct |
7 ms |
7888 KB |
Output is correct |
25 |
Correct |
4 ms |
7296 KB |
Output is correct |
26 |
Correct |
5 ms |
7248 KB |
Output is correct |
27 |
Correct |
8 ms |
8544 KB |
Output is correct |
28 |
Correct |
7 ms |
8024 KB |
Output is correct |
29 |
Correct |
6 ms |
8016 KB |
Output is correct |
30 |
Correct |
7 ms |
8024 KB |
Output is correct |
31 |
Correct |
4 ms |
7248 KB |
Output is correct |
32 |
Correct |
4 ms |
7376 KB |
Output is correct |
33 |
Correct |
4 ms |
7344 KB |
Output is correct |
34 |
Correct |
5 ms |
7376 KB |
Output is correct |
35 |
Correct |
4 ms |
7248 KB |
Output is correct |
36 |
Correct |
106 ms |
29820 KB |
Output is correct |
37 |
Correct |
4 ms |
7372 KB |
Output is correct |
38 |
Correct |
108 ms |
31252 KB |
Output is correct |
39 |
Correct |
104 ms |
30848 KB |
Output is correct |
40 |
Correct |
86 ms |
30504 KB |
Output is correct |
41 |
Correct |
96 ms |
33040 KB |
Output is correct |
42 |
Correct |
102 ms |
24692 KB |
Output is correct |
43 |
Correct |
126 ms |
22340 KB |
Output is correct |
44 |
Correct |
138 ms |
28036 KB |
Output is correct |
45 |
Correct |
139 ms |
28444 KB |
Output is correct |
46 |
Correct |
144 ms |
28104 KB |
Output is correct |
47 |
Correct |
116 ms |
26704 KB |
Output is correct |
48 |
Correct |
104 ms |
26604 KB |
Output is correct |
49 |
Correct |
89 ms |
25412 KB |
Output is correct |
50 |
Correct |
97 ms |
25296 KB |
Output is correct |
51 |
Correct |
74 ms |
30404 KB |
Output is correct |
52 |
Correct |
70 ms |
30276 KB |
Output is correct |
53 |
Correct |
61 ms |
17364 KB |
Output is correct |
54 |
Correct |
59 ms |
17372 KB |
Output is correct |
55 |
Correct |
112 ms |
23256 KB |
Output is correct |
56 |
Correct |
119 ms |
23576 KB |
Output is correct |
57 |
Correct |
143 ms |
29508 KB |
Output is correct |
58 |
Correct |
150 ms |
30192 KB |
Output is correct |
59 |
Correct |
133 ms |
27716 KB |
Output is correct |
60 |
Correct |
127 ms |
22876 KB |
Output is correct |
61 |
Correct |
108 ms |
26748 KB |
Output is correct |
62 |
Correct |
116 ms |
26796 KB |
Output is correct |
63 |
Correct |
108 ms |
26780 KB |
Output is correct |
64 |
Correct |
96 ms |
25472 KB |
Output is correct |
65 |
Correct |
173 ms |
34168 KB |
Output is correct |
66 |
Correct |
142 ms |
30516 KB |
Output is correct |
67 |
Correct |
119 ms |
26256 KB |
Output is correct |
68 |
Correct |
58 ms |
15812 KB |
Output is correct |
69 |
Correct |
52 ms |
15800 KB |
Output is correct |
70 |
Correct |
106 ms |
26768 KB |
Output is correct |
71 |
Correct |
88 ms |
25240 KB |
Output is correct |
72 |
Correct |
4 ms |
7364 KB |
Output is correct |
73 |
Correct |
7 ms |
7884 KB |
Output is correct |
74 |
Correct |
7 ms |
7888 KB |
Output is correct |
75 |
Correct |
4 ms |
7372 KB |
Output is correct |
76 |
Correct |
3 ms |
7372 KB |
Output is correct |
77 |
Correct |
8 ms |
8536 KB |
Output is correct |
78 |
Correct |
7 ms |
8012 KB |
Output is correct |
79 |
Correct |
7 ms |
8028 KB |
Output is correct |
80 |
Correct |
8 ms |
8120 KB |
Output is correct |
81 |
Correct |
4 ms |
7324 KB |
Output is correct |
82 |
Correct |
4 ms |
7380 KB |
Output is correct |
83 |
Correct |
4 ms |
7368 KB |
Output is correct |
84 |
Correct |
4 ms |
7372 KB |
Output is correct |
85 |
Correct |
3 ms |
7372 KB |
Output is correct |
86 |
Correct |
37 ms |
13708 KB |
Output is correct |
87 |
Correct |
38 ms |
13636 KB |
Output is correct |
88 |
Correct |
39 ms |
13712 KB |
Output is correct |
89 |
Correct |
9 ms |
8656 KB |
Output is correct |
90 |
Correct |
8 ms |
8032 KB |
Output is correct |
91 |
Correct |
41 ms |
13008 KB |
Output is correct |
92 |
Correct |
40 ms |
13024 KB |
Output is correct |
93 |
Correct |
3 ms |
7372 KB |
Output is correct |
94 |
Correct |
110 ms |
31568 KB |
Output is correct |
95 |
Correct |
104 ms |
31288 KB |
Output is correct |
96 |
Correct |
103 ms |
30892 KB |
Output is correct |
97 |
Correct |
89 ms |
30460 KB |
Output is correct |
98 |
Correct |
96 ms |
33092 KB |
Output is correct |
99 |
Correct |
146 ms |
32068 KB |
Output is correct |
100 |
Correct |
138 ms |
29304 KB |
Output is correct |
101 |
Correct |
150 ms |
30000 KB |
Output is correct |
102 |
Correct |
124 ms |
23036 KB |
Output is correct |
103 |
Correct |
103 ms |
26600 KB |
Output is correct |
104 |
Correct |
106 ms |
26820 KB |
Output is correct |
105 |
Correct |
102 ms |
26448 KB |
Output is correct |
106 |
Correct |
91 ms |
25360 KB |
Output is correct |
107 |
Correct |
87 ms |
25316 KB |
Output is correct |
108 |
Correct |
71 ms |
30336 KB |
Output is correct |
109 |
Correct |
71 ms |
30336 KB |
Output is correct |
110 |
Correct |
58 ms |
17376 KB |
Output is correct |
111 |
Correct |
58 ms |
17360 KB |
Output is correct |
112 |
Correct |
111 ms |
23188 KB |
Output is correct |
113 |
Correct |
111 ms |
23244 KB |
Output is correct |