이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {
cerr<<vars<<" = ";
string delim="";
(...,(cerr<<delim<<values,delim=", "));
cerr<<"\n";
}
#else
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {}
#endif
#define pb push_back
#define sz(x) (int)(x.size())
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<typename T> inline void maxa(T& a,T b){a=max(a,b);}
template<typename T> inline void mina(T& a,T b){a=min(a,b);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int mxN=1e5+5,mxL=20; //make sure this is right
const int mod=1e9+7;
vector<pii> graph[mxN];
vector<int> vt[mxN];
int sum[mxN],st[mxN],en[mxN],up[mxN][mxL],cur,ht[mxN];
vector<int> ans;
void dfs(int at,int p){
up[at][0]=~p?p:at;
for(int i=1;i<mxL;i++)
up[at][i]=up[up[at][i-1]][i-1];
st[at]=++cur;
for(auto &[i,e]:graph[at]){
if(i==p)
continue;
ht[i]=ht[at]+1;
dfs(i,at);
}
en[at]=++cur;
}
int jump(int a,int k){
for(int i=0;i<mxL;i++){
if(k&(1<<i))
a=up[a][i];
}
return a;
}
int lca(int a,int b){
if(ht[a]>ht[b])
swap(a,b);
b=jump(b,ht[b]-ht[a]);
if(a==b)
return a;
for(int i=19;i>=0;i--){
if(up[a][i]!=up[b][i]){
a=up[a][i];
b=up[b][i];
}
}
return up[a][0];
}
bool is_anc(int a,int b){return st[a]<=st[b] && en[a]>=en[b];}
void solve(int at,int p){
for(int &i:vt[at])
solve(i,at);
if(~p)
sum[at]++;
sum[at]-=sz(vt[at]);
}
void build(vector<int> &a){
sort(a.begin(),a.end(),[&](auto x,auto y){return st[x]<st[y];});
int k=sz(a);
for(int i=0;i<k-1;i++)
a.pb(lca(a[i],a[i+1]));
sort(a.begin(),a.end(),[&](auto x,auto y){return st[x]<st[y];});
a.resize(unique(a.begin(),a.end())-a.begin());
for(int &i:a)
vt[i].clear();
stack<int> stk; stk.push(a[0]);
for(int i=1;i<sz(a);i++){
while(sz(stk)>1 && !is_anc(stk.top(),a[i])){
int p=stk.top(); stk.pop();
vt[stk.top()].pb(p);
}
stk.push(a[i]);
}
while(sz(stk)>1){
int p=stk.top(); stk.pop();
vt[stk.top()].pb(p);
}
solve(stk.top(),-1);
}
void ps(int at,int p,int k){
for(auto &[i,e]:graph[at]){
if(i==p)
continue;
ps(i,at,k);
if(sum[i]>=k)
ans.pb(e);
sum[at]+=sum[i];
}
deb(at,sum[at]);
}
int main(){
cin.sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#ifdef LOCAL
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
int n,m,k; cin>>n>>m>>k;
for(int i=1;i<n;i++){
int a,b; cin>>a>>b;
graph[a].pb({b,i});
graph[b].pb({a,i});
}
dfs(1,-1);
for(int i=0;i<m;i++){
int s; cin>>s;
vector<int> a;
for(int j=0;j<s;j++){
int x; cin>>x;
a.pb(x);
}
build(a);
}
ps(1,-1,k);
cout<<sz(ans)<<"\n";
for(int i=0;i<sz(ans);i++)
cout<<ans[i]<<" \n"[i==sz(ans)-1];
}
컴파일 시 표준 에러 (stderr) 메시지
railway.cpp: In function 'void dfs(int, int)':
railway.cpp:42:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
42 | for(auto &[i,e]:graph[at]){
| ^
railway.cpp: In function 'void ps(int, int, int)':
railway.cpp:109:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
109 | for(auto &[i,e]:graph[at]){
| ^
# | 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... |