이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct node_t {
vector<int> anc, childs;
vector<vector<int>> path;
int depth;
};
vector<vector<pair<int, int>>> adj;
vector<node_t> tree;
void buildTree(int cur) {
for (auto& p : adj[cur]) {
if (not tree[cur].anc.empty() and tree[cur].anc[0] == p.first) continue;
tree[p.first].anc.push_back(cur);
tree[p.first].path.push_back({p.second});
tree[cur].childs.push_back(p.first);
tree[p.first].depth = tree[cur].depth + 1;
buildTree(p.first);
}
}
void buildAnc(int cur) {
int id = tree[cur].anc[0], step = 0;
while (tree[id].anc.size() >= step + 1) {
tree[cur].path.push_back({});
for (int road : tree[id].path[step]) tree[cur].path.back().push_back(road);
id = tree[id].anc[step];
tree[cur].anc.push_back(id);
step++;
}
for (int child : tree[cur].childs) buildAnc(child);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, k, i, j, tmp, tmp2;
cin >> n >> m >> k;
adj.resize(n + 1);
for (i = 1; i <= n - 1; i++) {
cin >> tmp >> tmp2;
adj[tmp].push_back(make_pair(tmp2, i));
adj[tmp2].push_back(make_pair(tmp, i));
}
vector<vector<int>> ms(m);
for (i = 0; i < m; i++) {
cin >> tmp;
ms[i].resize(tmp);
for (j = 0; j < tmp; j++) cin >> ms[i][j];
}
tree.resize(n + 1);
buildTree(1);
for (int child : tree[1].childs) buildAnc(child);
vector<int> cnt(n + 1);
for (auto& mi : ms) {
// find LCA of all selected cities
int LCA = mi[0], tu, tv, pos;
for (int city : mi) {
if (city == 1) {
LCA = 1;
break;
}
tu = LCA;
tv = city;
if (tree[tu].depth > tree[tv].depth) swap(tu, tv);
pos = tree[tv].anc.size() - 1;
while (tree[tv].depth > tree[tu].depth) {
while (tree[tree[tv].anc[pos]].depth < tree[tu].depth) pos--;
tv = tree[tv].anc[pos];
}
if (tv == tu) {
LCA = tu;
continue;
}
pos = tree[tv].anc.size() - 1;
while (true) {
while (pos >= 0 and tree[tv].anc[pos] == tree[tu].anc[pos]) pos--;
if (pos < 0) break;
tu = tree[tu].anc[pos];
tv = tree[tv].anc[pos];
}
LCA = tree[tu].anc[0];
}
unordered_set<int> req;
for (int city : mi) {
pos = tree[city].anc.size() - 1;
while (city != LCA) {
while (pos >= 0 and (pos >= tree[city].anc.size() or tree[tree[city].anc[pos]].depth < tree[LCA].depth)) pos--;
for (int i = 0; i <= pos; i++) {
for (int road : tree[city].path[i]) req.insert(road);
}
city = tree[city].anc[pos];
}
}
for (int elem : req) cnt[elem]++;
}
int ans = 0;
for (i = 0; i <= n; i++) {
if (cnt[i] >= k) ans++;
}
cout << ans << endl;
for (i = 0; i <= n; i++) {
if (cnt[i] >= k) cout << i << ' ';
}
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
railway.cpp: In function 'void buildAnc(int)':
railway.cpp:27:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
27 | while (tree[id].anc.size() >= step + 1) {
| ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
railway.cpp: In function 'int main()':
railway.cpp:92:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
92 | while (pos >= 0 and (pos >= tree[city].anc.size() or tree[tree[city].anc[pos]].depth < tree[LCA].depth)) pos--;
| ~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |