# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
124787 | 2019-07-04T02:00:26 Z | model_code | Railway (BOI17_railway) | C++17 | 267 ms | 35572 KB |
#include<iostream> #include<vector> #include<unordered_map> #include<cstdio> #include<algorithm> #include <cassert> using namespace std; int n, m, k; vector<vector<int> > T, ID, ministersInCity; vector<int> biggestChild, passiveMinisters, onDFSStack, ministerNumCities, importantTracks; void initialize() { scanf("%d%d%d", &n, &m, &k); passiveMinisters = vector<int> (n, 0); biggestChild = vector<int> (n, -1); //onDFSStack = vector<bool> (n, false); for(int i = 0; i < n; ++i) onDFSStack.push_back(false); T = vector<vector<int> > (n, vector<int>()); ID = vector<vector<int> > (n, vector<int>()); ministersInCity = vector<vector<int> > (n, vector<int>()); for(int i = 1; i <= n-1; ++i) { int u, v; scanf("%d%d", &u, &v); T[--u].push_back(--v); T[v].push_back(u); ID[u].push_back(i); ID[v].push_back(i); } ministerNumCities = vector<int> (m, 0); for(int i = 0; i < m; ++i) { int si; scanf("%d", &si); assert(si >= 1); ministerNumCities[i] = si; for(int j = 0; j < si; ++j) { int city; scanf("%d", &city); ministersInCity[--city].push_back(i); } } } // when this is over biggestChild[pos] = u for child u with largest subtree. int makeBiggestChildDFS(int pos) { onDFSStack[pos] = true; int biggestSize = -1, myBiggestChild = -1, ans = 1; for(int i = 0; i < T[pos].size(); ++i) { int ch = T[pos][i]; if(onDFSStack[ch]) continue; int mySize = makeBiggestChildDFS(ch); ans += mySize; if(biggestSize < mySize) { biggestSize = mySize; myBiggestChild = ch; } } biggestChild[pos] = myBiggestChild; onDFSStack[pos] = false; return ans; } // returns for each minister below the tree how many times he appears below the tree // sets passive-ministers = number of ministers that have appeared entirely in the subtree // counts the number of important edges void DFS(int pos, int edgeID, unordered_map<int, int> &ministers) { //cerr << "in " << pos << endl; onDFSStack[pos] = true; if(biggestChild[pos] >= 0) { int bigChildPos; for(bigChildPos = 0; bigChildPos < T[pos].size(); ++bigChildPos) {if(T[pos][bigChildPos] == biggestChild[pos]) break;} DFS(biggestChild[pos], ID[pos][bigChildPos], ministers); passiveMinisters[pos] = passiveMinisters[biggestChild[pos]]; } unordered_map<int, int> newMinisters; for(int i = 0; i < T[pos].size(); ++i) { int ch = T[pos][i]; int chID = ID[pos][i]; if(onDFSStack[ch] || ch == biggestChild[pos]) continue; newMinisters.clear(); DFS(ch, chID, newMinisters); for(auto it = newMinisters.begin(); it != newMinisters.end(); it++) { int minister = (*it).first; int numOccurences = (*it).second; int totalOccurences = ministers[minister] + numOccurences; ministers[minister] = totalOccurences; if(ministers[minister] == ministerNumCities[minister]) {passiveMinisters[pos]++;} } } for(int i = 0; i < ministersInCity[pos].size(); ++i) { int minister = ministersInCity[pos][i]; int totalOccurences = ministers[minister] + 1; ministers[minister] = totalOccurences; if(ministers[minister] == ministerNumCities[minister]) {passiveMinisters[pos]++;} } if(ministers.size() - passiveMinisters[pos] >= k) importantTracks.push_back(edgeID); onDFSStack[pos] = false; //cerr << "out " << pos << endl; } int main() { initialize(); makeBiggestChildDFS(0); unordered_map<int, int> dummy; DFS(0, -1, dummy); sort(importantTracks.begin(), importantTracks.end()); printf("%d\n", importantTracks.size()); for(int i = 0; i + 1 < importantTracks.size(); ++i) {printf("%d ", importantTracks[i]);} if(importantTracks.size() != 0) { printf("%d\n", importantTracks[importantTracks.size() - 1]); } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 348 KB | Output is correct |
2 | Correct | 12 ms | 1916 KB | Output is correct |
3 | Correct | 11 ms | 1784 KB | Output is correct |
4 | Correct | 2 ms | 256 KB | Output is correct |
5 | Correct | 2 ms | 376 KB | Output is correct |
6 | Correct | 22 ms | 2680 KB | Output is correct |
7 | Correct | 10 ms | 2040 KB | Output is correct |
8 | Correct | 8 ms | 2040 KB | Output is correct |
9 | Correct | 10 ms | 2040 KB | Output is correct |
10 | Correct | 2 ms | 252 KB | Output is correct |
11 | Correct | 2 ms | 380 KB | Output is correct |
12 | Correct | 2 ms | 256 KB | Output is correct |
13 | Correct | 2 ms | 376 KB | Output is correct |
14 | Correct | 2 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 348 KB | Output is correct |
2 | Correct | 12 ms | 1916 KB | Output is correct |
3 | Correct | 11 ms | 1784 KB | Output is correct |
4 | Correct | 2 ms | 256 KB | Output is correct |
5 | Correct | 2 ms | 376 KB | Output is correct |
6 | Correct | 22 ms | 2680 KB | Output is correct |
7 | Correct | 10 ms | 2040 KB | Output is correct |
8 | Correct | 8 ms | 2040 KB | Output is correct |
9 | Correct | 10 ms | 2040 KB | Output is correct |
10 | Correct | 2 ms | 252 KB | Output is correct |
11 | Correct | 2 ms | 380 KB | Output is correct |
12 | Correct | 2 ms | 256 KB | Output is correct |
13 | Correct | 2 ms | 376 KB | Output is correct |
14 | Correct | 2 ms | 376 KB | Output is correct |
15 | Correct | 41 ms | 2524 KB | Output is correct |
16 | Correct | 45 ms | 2552 KB | Output is correct |
17 | Correct | 42 ms | 2680 KB | Output is correct |
18 | Correct | 11 ms | 2724 KB | Output is correct |
19 | Correct | 10 ms | 2040 KB | Output is correct |
20 | Correct | 44 ms | 2808 KB | Output is correct |
21 | Correct | 44 ms | 2808 KB | Output is correct |
22 | Correct | 2 ms | 380 KB | Output is correct |
23 | Correct | 11 ms | 1784 KB | Output is correct |
24 | Correct | 10 ms | 1956 KB | Output is correct |
25 | Correct | 2 ms | 256 KB | Output is correct |
26 | Correct | 2 ms | 376 KB | Output is correct |
27 | Correct | 11 ms | 2652 KB | Output is correct |
28 | Correct | 10 ms | 2040 KB | Output is correct |
29 | Correct | 8 ms | 2040 KB | Output is correct |
30 | Correct | 9 ms | 2012 KB | Output is correct |
31 | Correct | 2 ms | 256 KB | Output is correct |
32 | Correct | 2 ms | 376 KB | Output is correct |
33 | Correct | 2 ms | 348 KB | Output is correct |
34 | Correct | 2 ms | 376 KB | Output is correct |
35 | Correct | 2 ms | 256 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 153 ms | 35572 KB | Output is correct |
2 | Correct | 2 ms | 256 KB | Output is correct |
3 | Correct | 146 ms | 35056 KB | Output is correct |
4 | Correct | 140 ms | 34672 KB | Output is correct |
5 | Correct | 143 ms | 33656 KB | Output is correct |
6 | Correct | 163 ms | 33656 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 137 ms | 25456 KB | Output is correct |
2 | Correct | 179 ms | 20180 KB | Output is correct |
3 | Correct | 201 ms | 19988 KB | Output is correct |
4 | Correct | 229 ms | 21892 KB | Output is correct |
5 | Correct | 217 ms | 19924 KB | Output is correct |
6 | Correct | 137 ms | 25560 KB | Output is correct |
7 | Correct | 139 ms | 25456 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 137 ms | 25456 KB | Output is correct |
2 | Correct | 179 ms | 20180 KB | Output is correct |
3 | Correct | 201 ms | 19988 KB | Output is correct |
4 | Correct | 229 ms | 21892 KB | Output is correct |
5 | Correct | 217 ms | 19924 KB | Output is correct |
6 | Correct | 137 ms | 25560 KB | Output is correct |
7 | Correct | 139 ms | 25456 KB | Output is correct |
8 | Correct | 146 ms | 25448 KB | Output is correct |
9 | Correct | 146 ms | 25556 KB | Output is correct |
10 | Correct | 129 ms | 33412 KB | Output is correct |
11 | Correct | 129 ms | 33572 KB | Output is correct |
12 | Correct | 110 ms | 17648 KB | Output is correct |
13 | Correct | 111 ms | 17712 KB | Output is correct |
14 | Correct | 173 ms | 16696 KB | Output is correct |
15 | Correct | 173 ms | 16372 KB | Output is correct |
16 | Correct | 226 ms | 21536 KB | Output is correct |
17 | Correct | 246 ms | 21756 KB | Output is correct |
18 | Correct | 211 ms | 21808 KB | Output is correct |
19 | Correct | 168 ms | 19184 KB | Output is correct |
20 | Correct | 140 ms | 25840 KB | Output is correct |
21 | Correct | 143 ms | 26096 KB | Output is correct |
22 | Correct | 140 ms | 25840 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 348 KB | Output is correct |
2 | Correct | 12 ms | 1916 KB | Output is correct |
3 | Correct | 11 ms | 1784 KB | Output is correct |
4 | Correct | 2 ms | 256 KB | Output is correct |
5 | Correct | 2 ms | 376 KB | Output is correct |
6 | Correct | 22 ms | 2680 KB | Output is correct |
7 | Correct | 10 ms | 2040 KB | Output is correct |
8 | Correct | 8 ms | 2040 KB | Output is correct |
9 | Correct | 10 ms | 2040 KB | Output is correct |
10 | Correct | 2 ms | 252 KB | Output is correct |
11 | Correct | 2 ms | 380 KB | Output is correct |
12 | Correct | 2 ms | 256 KB | Output is correct |
13 | Correct | 2 ms | 376 KB | Output is correct |
14 | Correct | 2 ms | 376 KB | Output is correct |
15 | Correct | 41 ms | 2524 KB | Output is correct |
16 | Correct | 45 ms | 2552 KB | Output is correct |
17 | Correct | 42 ms | 2680 KB | Output is correct |
18 | Correct | 11 ms | 2724 KB | Output is correct |
19 | Correct | 10 ms | 2040 KB | Output is correct |
20 | Correct | 44 ms | 2808 KB | Output is correct |
21 | Correct | 44 ms | 2808 KB | Output is correct |
22 | Correct | 2 ms | 380 KB | Output is correct |
23 | Correct | 11 ms | 1784 KB | Output is correct |
24 | Correct | 10 ms | 1956 KB | Output is correct |
25 | Correct | 2 ms | 256 KB | Output is correct |
26 | Correct | 2 ms | 376 KB | Output is correct |
27 | Correct | 11 ms | 2652 KB | Output is correct |
28 | Correct | 10 ms | 2040 KB | Output is correct |
29 | Correct | 8 ms | 2040 KB | Output is correct |
30 | Correct | 9 ms | 2012 KB | Output is correct |
31 | Correct | 2 ms | 256 KB | Output is correct |
32 | Correct | 2 ms | 376 KB | Output is correct |
33 | Correct | 2 ms | 348 KB | Output is correct |
34 | Correct | 2 ms | 376 KB | Output is correct |
35 | Correct | 2 ms | 256 KB | Output is correct |
36 | Correct | 153 ms | 35572 KB | Output is correct |
37 | Correct | 2 ms | 256 KB | Output is correct |
38 | Correct | 146 ms | 35056 KB | Output is correct |
39 | Correct | 140 ms | 34672 KB | Output is correct |
40 | Correct | 143 ms | 33656 KB | Output is correct |
41 | Correct | 163 ms | 33656 KB | Output is correct |
42 | Correct | 137 ms | 25456 KB | Output is correct |
43 | Correct | 179 ms | 20180 KB | Output is correct |
44 | Correct | 201 ms | 19988 KB | Output is correct |
45 | Correct | 229 ms | 21892 KB | Output is correct |
46 | Correct | 217 ms | 19924 KB | Output is correct |
47 | Correct | 137 ms | 25560 KB | Output is correct |
48 | Correct | 139 ms | 25456 KB | Output is correct |
49 | Correct | 146 ms | 25448 KB | Output is correct |
50 | Correct | 146 ms | 25556 KB | Output is correct |
51 | Correct | 129 ms | 33412 KB | Output is correct |
52 | Correct | 129 ms | 33572 KB | Output is correct |
53 | Correct | 110 ms | 17648 KB | Output is correct |
54 | Correct | 111 ms | 17712 KB | Output is correct |
55 | Correct | 173 ms | 16696 KB | Output is correct |
56 | Correct | 173 ms | 16372 KB | Output is correct |
57 | Correct | 226 ms | 21536 KB | Output is correct |
58 | Correct | 246 ms | 21756 KB | Output is correct |
59 | Correct | 211 ms | 21808 KB | Output is correct |
60 | Correct | 168 ms | 19184 KB | Output is correct |
61 | Correct | 140 ms | 25840 KB | Output is correct |
62 | Correct | 143 ms | 26096 KB | Output is correct |
63 | Correct | 140 ms | 25840 KB | Output is correct |
64 | Correct | 151 ms | 26324 KB | Output is correct |
65 | Correct | 267 ms | 20316 KB | Output is correct |
66 | Correct | 209 ms | 17648 KB | Output is correct |
67 | Correct | 208 ms | 17364 KB | Output is correct |
68 | Correct | 115 ms | 17364 KB | Output is correct |
69 | Correct | 111 ms | 17264 KB | Output is correct |
70 | Correct | 155 ms | 26836 KB | Output is correct |
71 | Correct | 146 ms | 25544 KB | Output is correct |
72 | Correct | 2 ms | 376 KB | Output is correct |
73 | Correct | 10 ms | 1912 KB | Output is correct |
74 | Correct | 10 ms | 1784 KB | Output is correct |
75 | Correct | 2 ms | 256 KB | Output is correct |
76 | Correct | 2 ms | 376 KB | Output is correct |
77 | Correct | 11 ms | 2680 KB | Output is correct |
78 | Correct | 10 ms | 2012 KB | Output is correct |
79 | Correct | 8 ms | 2040 KB | Output is correct |
80 | Correct | 9 ms | 2040 KB | Output is correct |
81 | Correct | 2 ms | 376 KB | Output is correct |
82 | Correct | 2 ms | 292 KB | Output is correct |
83 | Correct | 2 ms | 256 KB | Output is correct |
84 | Correct | 2 ms | 252 KB | Output is correct |
85 | Correct | 2 ms | 256 KB | Output is correct |
86 | Correct | 43 ms | 2552 KB | Output is correct |
87 | Correct | 45 ms | 2552 KB | Output is correct |
88 | Correct | 42 ms | 2680 KB | Output is correct |
89 | Correct | 11 ms | 2680 KB | Output is correct |
90 | Correct | 11 ms | 2040 KB | Output is correct |
91 | Correct | 44 ms | 2728 KB | Output is correct |
92 | Correct | 44 ms | 2684 KB | Output is correct |
93 | Correct | 2 ms | 376 KB | Output is correct |
94 | Correct | 153 ms | 35540 KB | Output is correct |
95 | Correct | 171 ms | 35076 KB | Output is correct |
96 | Correct | 148 ms | 34572 KB | Output is correct |
97 | Correct | 136 ms | 33648 KB | Output is correct |
98 | Correct | 130 ms | 33436 KB | Output is correct |
99 | Correct | 214 ms | 22068 KB | Output is correct |
100 | Correct | 222 ms | 21908 KB | Output is correct |
101 | Correct | 249 ms | 21808 KB | Output is correct |
102 | Correct | 177 ms | 20352 KB | Output is correct |
103 | Correct | 140 ms | 25584 KB | Output is correct |
104 | Correct | 141 ms | 26068 KB | Output is correct |
105 | Correct | 139 ms | 25564 KB | Output is correct |
106 | Correct | 145 ms | 25712 KB | Output is correct |
107 | Correct | 145 ms | 25456 KB | Output is correct |
108 | Correct | 127 ms | 33452 KB | Output is correct |
109 | Correct | 127 ms | 33392 KB | Output is correct |
110 | Correct | 112 ms | 17904 KB | Output is correct |
111 | Correct | 107 ms | 17648 KB | Output is correct |
112 | Correct | 165 ms | 16368 KB | Output is correct |
113 | Correct | 164 ms | 16572 KB | Output is correct |