이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define fileIO(name) if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
#define SPEED ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define epl emplace
#define eb emplace_back
#define EL cout << '\n'
#define dbg(x) cout << #x << " = " << (x) << ' '
#define dbgp(x) cout << #x << " = (" << (x.fi) << ", " << (x.se) << ") "
#define fi first
#define se second
#define mp make_pair
#define sqr(x) (x) * (x)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define lwb lower_bound
#define upb upper_bound
#define ctz __builtin_ctzll
#define pct __builtin_popcountll
using namespace std;
typedef long long ll;
typedef long double ldb;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
typedef pair<int, int> pii;
typedef pair<ldb, ldb> pld;
typedef pair<double, double> pdd;
template<class T1, class T2> bool minimize(T1 &a, T2 &b){return a > b ? a = b, true : false;}
template<class T1, class T2> bool maximize(T1 &a, T2 &b){return a < b ? a = b, true : false;}
const int N = 1e5 + 3;
int n, m, k, node[N], cnt[N];
int Tin[N], Timer, jmp[N][18], dep[N];
bool mark[N];
vector<int> res;
vector<pii> adj[N];
void dfsLca(int u, int par){
Tin[u] = ++Timer;
for(int i = 0; i < adj[u].size(); ++i){
int v = adj[u][i].fi;
if(v == par) continue;
jmp[v][0] = u; dep[v] = dep[u] + 1;
for(int j = 1; j <= 17; ++j){
if(!jmp[v][j - 1]) break;
jmp[v][j] = jmp[jmp[v][j - 1]][j - 1];
}
dfsLca(v, u);
}
}
bool cmp(const int &a, const int &b){
return Tin[a] < Tin[b];
}
int Lca(int u, int v){
if(dep[u] < dep[v]) swap(u, v);
for(int i = 17; i >= 0; --i) if(dep[u] - (1 << i) >= dep[v]){
u = jmp[u][i];
}
if(u == v) return u;
for(int i = 17; i >= 0; --i) if(jmp[u][i] != jmp[v][i]){
u = jmp[u][i]; v = jmp[v][i];
}
return jmp[u][0];
}
void dfs(int u, int pre_id){
for(int i = 0; i < adj[u].size(); ++i){
int v, id; tie(v, id) = adj[u][i];
if(id == pre_id) continue;
dfs(v, id); cnt[u] += cnt[v];
}
if(pre_id && cnt[u] / 2 >= k) res.eb(pre_id);
}
int main(){
SPEED;
cin >> n >> m >> k;
for(int i = 1; i < n; ++i){
int u, v; cin >> u >> v;
adj[u].eb(v, i); adj[v].eb(u, i);
}
dfsLca(1, 0);
while(m--){
int sz; cin >> sz;
for(int i = 1; i <= sz; ++i) cin >> node[i];
sort(node + 1, node + 1 + sz, cmp);
node[sz + 1] = node[1];
for(int i = 1; i <= sz; ++i){
int u = node[i], v = node[i + 1];
int lca = Lca(u, v);
++cnt[u]; ++cnt[v]; cnt[lca] -= 2;
}
}
dfs(1, 0);
cout << res.size() << '\n';
for(int &x : res) cout << x << ' ';
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
railway.cpp: In function 'void dfsLca(int, int)':
railway.cpp:50:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for(int i = 0; i < adj[u].size(); ++i){
| ~~^~~~~~~~~~~~~~~
railway.cpp: In function 'void dfs(int, int)':
railway.cpp:76:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | for(int i = 0; i < adj[u].size(); ++i){
| ~~^~~~~~~~~~~~~~~
# | 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... |