이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <list>
using namespace std;
using ll = long long int;
vector<int> g[100100];
int dp[100100][30];
map<int, int> in[100100], out[100100];
int level[100100];
map<pair<int,int>,int> id;
vector<int> ans;
int k;
void dfs(int node, int prev = 0, int l = 1){
level[node] = l;
dp[node][0] = prev;
for(auto i : g[node]){
if(i != prev){
dfs(i, node, l + 1);
}
}
}
int jump(int a, int x){
for(int i = 0; i < 20; ++i){
if((x >> i) & 1){
a = dp[a][i];
}
}
return a;
}
int lca(int a, int b){
if(level[a] < level[b]) swap(a,b);
a = jump(a, level[a] - level[b]);
if(a == b) return a;
for(int i = 20; i >= 0; --i){
if(dp[a][i] != dp[b][i]){
a = dp[a][i], b = dp[b][i];
}
}
return dp[a][0];
}
pair<map<int,int>,int> solve(int node, int prev = -1){
map<int,int> open; int ctr = 0;
for(auto i : g[node]){
if(i != prev){
auto a = solve(i, node);
if(a.first.size() >= k){
ans.push_back(id[{node, i}]);
}
//if(a.first.size() > open.size()) swap(a.first, open);
for(auto& j : a.first){
if(open[j.first] == 0) ++ctr;
open[j.first] += j.second;
}
}
}
for(auto& i : out[node]){
open[i.first] -= i.second;
if(open[i.first] == 0) open.erase(i.first);
}
for(auto& i : in[node]){
open[i.first] += i.second;
if(open[i.first] == 0) open.erase(i.first);
}
/*cerr << node << ": ";
for(auto i : open){
cerr << i.first << " " << i.second << endl;
}
cerr << endl;*/
return {open, ctr};
}
int main()
{
int n, m;
cin >> n >> m >> k;
for(int i = 0; i < n - 1; ++i){
ll a, b;
cin >> a >> b;
g[a].emplace_back(b), g[b].emplace_back(a);
id[{a,b}] = id[{b,a}] = i + 1;
}
dfs(1);
for(int i = 1; i < 20; ++i){
for(int node = 1; node <= n; ++node){
dp[node][i] = dp[dp[node][i - 1]][i - 1];
}
}
while(m--){
int meret;
cin >> meret;
vector<int> v(meret);
for(auto& i : v) cin >> i;
for(int i = 1; i < meret; ++i){
int c = lca(v[i], v[0]);
//if(c != v[i])
in[v[i]][m]++;
// if(c != v[0])
in[v[0]][m]++;
out[c][m] += 2;
}
}
solve(1);
sort(begin(ans), end(ans));
cout << ans.size() << endl;
for(auto& i : ans){
cout << i << " ";
}
if(ans.size() > 0)
cout << endl;
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
railway.cpp: In function 'std::pair<std::map<int, int>, int> solve(int, int)':
railway.cpp:58:25: warning: comparison of integer expressions of different signedness: 'std::map<int, int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
58 | if(a.first.size() >= k){
| ~~~~~~~~~~~~~~~^~~~
# | 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... |