#include <bits/stdc++.h>
using namespace std ;
#define int int64_t //be careful about this
#define endl "\n"
#define f(i,a,b) for(int i=int(a);i<int(b);++i)
#define pr pair
#define ar array
#define fr first
#define sc second
#define vt vector
#define pb push_back
#define eb emplace_back
#define LB lower_bound
#define UB upper_bound
#define PQ priority_queue
#define sz(x) ((int)(x).size())
#define all(a) (a).begin(),(a).end()
#define allr(a) (a).rbegin(),(a).rend()
#define mem(a,b) memset(a, b, sizeof(a))
template<class A> void rd(vt<A>& v);
template<class T> void rd(T& x){ cin >> x; }
template<class H, class... T> void rd(H& h, T&... t) { rd(h) ; rd(t...) ;}
template<class A> void rd(vt<A>& x) { for(auto& a : x) rd(a) ;}
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
template<typename T>
void __p(T a) {
cout<<a;
}
template<typename T, typename F>
void __p(pair<T, F> a) {
cout<<"{";
__p(a.first);
cout<<",";
__p(a.second);
cout<<"}\n";
}
template<typename T>
void __p(std::vector<T> a) {
cout<<"{";
for(auto it=a.begin(); it<a.end(); it++)
__p(*it),cout<<",}\n"[it+1==a.end()];
}
template<typename T, typename ...Arg>
void __p(T a1, Arg ...a) {
__p(a1);
__p(a...);
}
template<typename Arg1>
void __f(const char *name, Arg1 &&arg1) {
cout<<name<<" : ";
__p(arg1);
cout<<endl;
}
template<typename Arg1, typename ... Args>
void __f(const char *names, Arg1 &&arg1, Args &&... args) {
int bracket=0,i=0;
for(;; i++)
if(names[i]==','&&bracket==0)
break;
else if(names[i]=='(')
bracket++;
else if(names[i]==')')
bracket--;
const char *comma=names+i;
cout.write(names,comma-names)<<" : ";
__p(arg1);
cout<<" | ";
__f(comma+1,args...);
}
void setIO(string s = "") {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin.exceptions(cin.failbit);
cout.precision(15); cout << fixed;
if(sz(s)){
freopen((s+".in").c_str(),"r",stdin);
freopen((s+".out").c_str(),"w",stdout);
}
}
struct LCA {
int N, timer = 0, LOG ;
vector< vector<int> > up, dis, max_edge ;
vector< vector<array<int,2> > > adj ;
vector<int> tin, tout, depth ;
void init(int _N) {
N = _N ; LOG = log2(N) + 5 ;
adj.resize(N) ;
up.resize(N, vector<int> (LOG)) ;
dis.resize(N, vector<int> (LOG)) ;
max_edge.resize(N, vector<int> (LOG)) ;
tin = tout = depth = vector<int> (N) ;
}
void ae(int x, int y,int w = 1) { // add edge
adj[x].push_back({y,w}), adj[y].push_back({x,w});
}
void dfs(int v, int p, int w){
tin[v] = ++timer;
up[v][0] = p;
dis[v][0] = w ;
max_edge[v][0] = w ;
for(int i = 1; i < LOG; i++){
up[v][i] = up[up[v][i-1]][i-1] ;
dis[v][i] = dis[v][i-1] + dis[up[v][i-1]][i-1] ;
max_edge[v][i] = max(max_edge[v][i-1],max_edge[up[v][i-1]][i-1]) ;
}
for(auto arr:adj[v]){
int u = arr[0], w = arr[1];
if(u != p){
depth[u] = depth[v] + 1 ; dfs(u,v,w) ;
}
}
tout[v] = ++timer;
}
void gen(int R = 0) {
depth[R] = 0 ;
dfs(R,R,0);
}
bool is_ancestor(int u, int v){
return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int lca(int u, int v){
if( is_ancestor(u,v) ) return u;
if( is_ancestor(v,u) ) return v;
for(int i=LOG-1;i>=0;--i) {
if( !is_ancestor(up[u][i],v) ){
u = up[u][i] ;
}
}
return up[u][0];
}
int dist(int u, int v) {
return depth[u] + depth[v] - 2*depth[lca(u,v)];
}
int weighted_dist(int u,int v){
int temp = lca(u,v);
int x1 = kth_ancestor_weighted_dist(u,depth[u] - depth[temp]);
int x2 = kth_ancestor_weighted_dist(v,depth[v] - depth[temp]);
return x1 + x2 ;
}
int weighted_max_edge(int u,int v){
int temp = lca(u,v);
int x1 = kth_ancestor_weighted_max_edge(u,depth[u] - depth[temp]);
int x2 = kth_ancestor_weighted_max_edge(v,depth[v] - depth[temp]);
return max(x1, x2) ;
}
int kth_ancestor(int i,int k){
if(depth[i] < k) return int(-1) ;
for(int j = LOG - 1; j >= 0; --j){
if( (int(1) << j) <= k ){
k -= (int(1) << j) ; i = up[i][j] ;
}
}
return i ;
}
int kth_ancestor_weighted_dist(int i,int k){
if(depth[i] < k) return int(-1) ;
int ans = 0 ;
for(int j = LOG - 1; j >= 0; --j){
if( (int(1) << j) <= k ){
k -= (int(1) << j) ;
ans += dis[i][j] ;
i = up[i][j] ;
}
}
return ans ;
}
int kth_ancestor_weighted_max_edge(int i,int k){
if(depth[i] < k) return int(-1) ;
int ans = 0 ;
for(int j = LOG - 1; j >= 0; --j){
if( (int(1) << j) <= k ){
k -= (int(1) << j) ;
ckmax(ans,max_edge[i][j]) ;
i = up[i][j] ;
}
}
return ans ;
}
int d(int i){
return depth[i];
}
};
LCA tree;
const int MAX_N = 1e5 + 7;
vector<int> g[MAX_N], st(MAX_N), en(MAX_N), par(MAX_N);
int timer = 1;
void dfs(int i, int p){
st[i] = timer++ ;
par[i] = p;
for(auto j:g[i]) if(j!=p){
dfs(j, i);
}
en[i] = timer - 1 ;
}
template <class T, int ...Ns> struct BIT {
T val = 0; void upd(T v) { val += v; }
T query() { return val; }
};
template <class T, int N, int... Ns> struct BIT<T, N, Ns...> {
BIT<T,Ns...> bit[N+1];
template<typename... Args> void upd(int pos, Args... args) { assert(pos > 0);
for (; pos<=N; pos+=pos&-pos) bit[pos].upd(args...); }
template<typename... Args> T sum(int r, Args... args) {
T res=0; for (;r;r-=r&-r) res += bit[r].query(args...);
return res; }
template<typename... Args> T query(int l, int r, Args...
args) { return sum(r,args...)-sum(l-1,args...); }
};
BIT<int,MAX_N> bit;
signed main(){
setIO();
int n,m,k; rd(n,m,k);
tree.init(n);
vt<ar<int,2>> edges;
f(_,0,n-1){
int u,v; rd(u,v);
edges.pb({--u,--v});
tree.ae(u,v);
g[u].pb(v);
g[v].pb(u);
}
tree.gen(0);
dfs(0,0);
set<pr<int,int>> node[n];
f(j,0,m){
int SZ; rd(SZ);
vt<int> a(SZ);
for(auto& i : a) rd(i),--i;
int x = a[0];
for(auto i : a){
x = tree.lca(i,x);
bit.upd(st[i],1);// ude bit to get end points.
}
int d = tree.d(x);
for(auto i : a){
if(bit.query(st[i],en[i]) == 1){
node[i].insert({-d,j});
}
}
for(auto i : a) bit.upd(st[i],-1);
}
vt<int> value(n);
function<void(int)> small_to_large = [&](int i){
for(auto j : g[i]) if(j != par[i]){
small_to_large(j);
// merge j and i;
if( sz(node[j]) > sz(node[i]) ) node[i].swap(node[j]);
for(auto p : node[j]) node[i].insert(p);
node[j].clear();
}
int d = -1 * tree.d(i);
while(sz(node[i]) && node[i].begin()->first <= d){
node[i].erase(node[i].begin());
}
value[i] = sz(node[i]);
};
small_to_large(0);
set<pr<int,int>> good;
f(i,0,n) if(value[i] >= k) good.insert({i,par[i]});
vt<int> ans;
f(i,0,n-1){
auto [u,v] = edges[i];
if(good.count({u,v}) || good.count({v,u})) ans.pb(i);
}
cout << sz(ans) << endl;
for(auto i : ans) cout << i + 1 << " " ;
}
Compilation message
railway.cpp: In function 'void setIO(std::string)':
railway.cpp:84:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
84 | freopen((s+".in").c_str(),"r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
railway.cpp:85:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
85 | freopen((s+".out").c_str(),"w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5068 KB |
Output is correct |
2 |
Correct |
22 ms |
12744 KB |
Output is correct |
3 |
Correct |
19 ms |
12688 KB |
Output is correct |
4 |
Correct |
3 ms |
5040 KB |
Output is correct |
5 |
Correct |
3 ms |
5040 KB |
Output is correct |
6 |
Correct |
23 ms |
13880 KB |
Output is correct |
7 |
Correct |
20 ms |
12936 KB |
Output is correct |
8 |
Correct |
21 ms |
12732 KB |
Output is correct |
9 |
Correct |
19 ms |
12860 KB |
Output is correct |
10 |
Correct |
3 ms |
5068 KB |
Output is correct |
11 |
Correct |
3 ms |
5068 KB |
Output is correct |
12 |
Correct |
3 ms |
5068 KB |
Output is correct |
13 |
Correct |
3 ms |
5068 KB |
Output is correct |
14 |
Correct |
3 ms |
5068 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5068 KB |
Output is correct |
2 |
Correct |
22 ms |
12744 KB |
Output is correct |
3 |
Correct |
19 ms |
12688 KB |
Output is correct |
4 |
Correct |
3 ms |
5040 KB |
Output is correct |
5 |
Correct |
3 ms |
5040 KB |
Output is correct |
6 |
Correct |
23 ms |
13880 KB |
Output is correct |
7 |
Correct |
20 ms |
12936 KB |
Output is correct |
8 |
Correct |
21 ms |
12732 KB |
Output is correct |
9 |
Correct |
19 ms |
12860 KB |
Output is correct |
10 |
Correct |
3 ms |
5068 KB |
Output is correct |
11 |
Correct |
3 ms |
5068 KB |
Output is correct |
12 |
Correct |
3 ms |
5068 KB |
Output is correct |
13 |
Correct |
3 ms |
5068 KB |
Output is correct |
14 |
Correct |
3 ms |
5068 KB |
Output is correct |
15 |
Correct |
56 ms |
16056 KB |
Output is correct |
16 |
Correct |
63 ms |
16000 KB |
Output is correct |
17 |
Correct |
60 ms |
16108 KB |
Output is correct |
18 |
Correct |
24 ms |
13824 KB |
Output is correct |
19 |
Correct |
29 ms |
12992 KB |
Output is correct |
20 |
Correct |
101 ms |
19504 KB |
Output is correct |
21 |
Correct |
95 ms |
19348 KB |
Output is correct |
22 |
Correct |
3 ms |
5068 KB |
Output is correct |
23 |
Correct |
23 ms |
12744 KB |
Output is correct |
24 |
Correct |
20 ms |
12744 KB |
Output is correct |
25 |
Correct |
4 ms |
5040 KB |
Output is correct |
26 |
Correct |
4 ms |
5068 KB |
Output is correct |
27 |
Correct |
26 ms |
13948 KB |
Output is correct |
28 |
Correct |
22 ms |
12908 KB |
Output is correct |
29 |
Correct |
17 ms |
12720 KB |
Output is correct |
30 |
Correct |
20 ms |
12872 KB |
Output is correct |
31 |
Correct |
4 ms |
5068 KB |
Output is correct |
32 |
Correct |
3 ms |
5044 KB |
Output is correct |
33 |
Correct |
3 ms |
5068 KB |
Output is correct |
34 |
Correct |
3 ms |
5068 KB |
Output is correct |
35 |
Correct |
3 ms |
5068 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
333 ms |
110004 KB |
Output is correct |
2 |
Correct |
3 ms |
5068 KB |
Output is correct |
3 |
Correct |
313 ms |
107316 KB |
Output is correct |
4 |
Correct |
282 ms |
106244 KB |
Output is correct |
5 |
Correct |
286 ms |
110532 KB |
Output is correct |
6 |
Correct |
305 ms |
111548 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
345 ms |
99216 KB |
Output is correct |
2 |
Correct |
383 ms |
93348 KB |
Output is correct |
3 |
Correct |
463 ms |
93620 KB |
Output is correct |
4 |
Correct |
402 ms |
93364 KB |
Output is correct |
5 |
Correct |
410 ms |
93520 KB |
Output is correct |
6 |
Correct |
336 ms |
99204 KB |
Output is correct |
7 |
Correct |
321 ms |
98884 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
345 ms |
99216 KB |
Output is correct |
2 |
Correct |
383 ms |
93348 KB |
Output is correct |
3 |
Correct |
463 ms |
93620 KB |
Output is correct |
4 |
Correct |
402 ms |
93364 KB |
Output is correct |
5 |
Correct |
410 ms |
93520 KB |
Output is correct |
6 |
Correct |
336 ms |
99204 KB |
Output is correct |
7 |
Correct |
321 ms |
98884 KB |
Output is correct |
8 |
Correct |
362 ms |
99468 KB |
Output is correct |
9 |
Correct |
319 ms |
99120 KB |
Output is correct |
10 |
Correct |
271 ms |
111340 KB |
Output is correct |
11 |
Correct |
297 ms |
111028 KB |
Output is correct |
12 |
Correct |
243 ms |
92532 KB |
Output is correct |
13 |
Correct |
238 ms |
92584 KB |
Output is correct |
14 |
Correct |
359 ms |
92064 KB |
Output is correct |
15 |
Correct |
359 ms |
92244 KB |
Output is correct |
16 |
Correct |
462 ms |
93580 KB |
Output is correct |
17 |
Correct |
442 ms |
93628 KB |
Output is correct |
18 |
Correct |
435 ms |
93440 KB |
Output is correct |
19 |
Correct |
419 ms |
93632 KB |
Output is correct |
20 |
Correct |
352 ms |
99612 KB |
Output is correct |
21 |
Correct |
369 ms |
99932 KB |
Output is correct |
22 |
Correct |
360 ms |
99772 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5068 KB |
Output is correct |
2 |
Correct |
22 ms |
12744 KB |
Output is correct |
3 |
Correct |
19 ms |
12688 KB |
Output is correct |
4 |
Correct |
3 ms |
5040 KB |
Output is correct |
5 |
Correct |
3 ms |
5040 KB |
Output is correct |
6 |
Correct |
23 ms |
13880 KB |
Output is correct |
7 |
Correct |
20 ms |
12936 KB |
Output is correct |
8 |
Correct |
21 ms |
12732 KB |
Output is correct |
9 |
Correct |
19 ms |
12860 KB |
Output is correct |
10 |
Correct |
3 ms |
5068 KB |
Output is correct |
11 |
Correct |
3 ms |
5068 KB |
Output is correct |
12 |
Correct |
3 ms |
5068 KB |
Output is correct |
13 |
Correct |
3 ms |
5068 KB |
Output is correct |
14 |
Correct |
3 ms |
5068 KB |
Output is correct |
15 |
Correct |
56 ms |
16056 KB |
Output is correct |
16 |
Correct |
63 ms |
16000 KB |
Output is correct |
17 |
Correct |
60 ms |
16108 KB |
Output is correct |
18 |
Correct |
24 ms |
13824 KB |
Output is correct |
19 |
Correct |
29 ms |
12992 KB |
Output is correct |
20 |
Correct |
101 ms |
19504 KB |
Output is correct |
21 |
Correct |
95 ms |
19348 KB |
Output is correct |
22 |
Correct |
3 ms |
5068 KB |
Output is correct |
23 |
Correct |
23 ms |
12744 KB |
Output is correct |
24 |
Correct |
20 ms |
12744 KB |
Output is correct |
25 |
Correct |
4 ms |
5040 KB |
Output is correct |
26 |
Correct |
4 ms |
5068 KB |
Output is correct |
27 |
Correct |
26 ms |
13948 KB |
Output is correct |
28 |
Correct |
22 ms |
12908 KB |
Output is correct |
29 |
Correct |
17 ms |
12720 KB |
Output is correct |
30 |
Correct |
20 ms |
12872 KB |
Output is correct |
31 |
Correct |
4 ms |
5068 KB |
Output is correct |
32 |
Correct |
3 ms |
5044 KB |
Output is correct |
33 |
Correct |
3 ms |
5068 KB |
Output is correct |
34 |
Correct |
3 ms |
5068 KB |
Output is correct |
35 |
Correct |
3 ms |
5068 KB |
Output is correct |
36 |
Correct |
333 ms |
110004 KB |
Output is correct |
37 |
Correct |
3 ms |
5068 KB |
Output is correct |
38 |
Correct |
313 ms |
107316 KB |
Output is correct |
39 |
Correct |
282 ms |
106244 KB |
Output is correct |
40 |
Correct |
286 ms |
110532 KB |
Output is correct |
41 |
Correct |
305 ms |
111548 KB |
Output is correct |
42 |
Correct |
345 ms |
99216 KB |
Output is correct |
43 |
Correct |
383 ms |
93348 KB |
Output is correct |
44 |
Correct |
463 ms |
93620 KB |
Output is correct |
45 |
Correct |
402 ms |
93364 KB |
Output is correct |
46 |
Correct |
410 ms |
93520 KB |
Output is correct |
47 |
Correct |
336 ms |
99204 KB |
Output is correct |
48 |
Correct |
321 ms |
98884 KB |
Output is correct |
49 |
Correct |
362 ms |
99468 KB |
Output is correct |
50 |
Correct |
319 ms |
99120 KB |
Output is correct |
51 |
Correct |
271 ms |
111340 KB |
Output is correct |
52 |
Correct |
297 ms |
111028 KB |
Output is correct |
53 |
Correct |
243 ms |
92532 KB |
Output is correct |
54 |
Correct |
238 ms |
92584 KB |
Output is correct |
55 |
Correct |
359 ms |
92064 KB |
Output is correct |
56 |
Correct |
359 ms |
92244 KB |
Output is correct |
57 |
Correct |
462 ms |
93580 KB |
Output is correct |
58 |
Correct |
442 ms |
93628 KB |
Output is correct |
59 |
Correct |
435 ms |
93440 KB |
Output is correct |
60 |
Correct |
419 ms |
93632 KB |
Output is correct |
61 |
Correct |
352 ms |
99612 KB |
Output is correct |
62 |
Correct |
369 ms |
99932 KB |
Output is correct |
63 |
Correct |
360 ms |
99772 KB |
Output is correct |
64 |
Correct |
356 ms |
100276 KB |
Output is correct |
65 |
Correct |
469 ms |
93356 KB |
Output is correct |
66 |
Correct |
409 ms |
93140 KB |
Output is correct |
67 |
Correct |
380 ms |
92212 KB |
Output is correct |
68 |
Correct |
230 ms |
89888 KB |
Output is correct |
69 |
Correct |
233 ms |
89908 KB |
Output is correct |
70 |
Correct |
353 ms |
101660 KB |
Output is correct |
71 |
Correct |
324 ms |
99120 KB |
Output is correct |
72 |
Correct |
3 ms |
5068 KB |
Output is correct |
73 |
Correct |
20 ms |
12784 KB |
Output is correct |
74 |
Correct |
20 ms |
12744 KB |
Output is correct |
75 |
Correct |
3 ms |
5044 KB |
Output is correct |
76 |
Correct |
3 ms |
5068 KB |
Output is correct |
77 |
Correct |
23 ms |
13992 KB |
Output is correct |
78 |
Correct |
20 ms |
12904 KB |
Output is correct |
79 |
Correct |
17 ms |
12760 KB |
Output is correct |
80 |
Correct |
18 ms |
12880 KB |
Output is correct |
81 |
Correct |
3 ms |
5068 KB |
Output is correct |
82 |
Correct |
3 ms |
5068 KB |
Output is correct |
83 |
Correct |
3 ms |
5036 KB |
Output is correct |
84 |
Correct |
3 ms |
5068 KB |
Output is correct |
85 |
Correct |
4 ms |
5044 KB |
Output is correct |
86 |
Correct |
56 ms |
16036 KB |
Output is correct |
87 |
Correct |
63 ms |
16036 KB |
Output is correct |
88 |
Correct |
82 ms |
16204 KB |
Output is correct |
89 |
Correct |
28 ms |
13768 KB |
Output is correct |
90 |
Correct |
22 ms |
13000 KB |
Output is correct |
91 |
Correct |
80 ms |
19428 KB |
Output is correct |
92 |
Correct |
91 ms |
19392 KB |
Output is correct |
93 |
Correct |
3 ms |
5068 KB |
Output is correct |
94 |
Correct |
304 ms |
110068 KB |
Output is correct |
95 |
Correct |
297 ms |
107444 KB |
Output is correct |
96 |
Correct |
282 ms |
106208 KB |
Output is correct |
97 |
Correct |
274 ms |
110516 KB |
Output is correct |
98 |
Correct |
295 ms |
111648 KB |
Output is correct |
99 |
Correct |
452 ms |
93364 KB |
Output is correct |
100 |
Correct |
457 ms |
93564 KB |
Output is correct |
101 |
Correct |
431 ms |
93692 KB |
Output is correct |
102 |
Correct |
377 ms |
93376 KB |
Output is correct |
103 |
Correct |
322 ms |
99068 KB |
Output is correct |
104 |
Correct |
348 ms |
99280 KB |
Output is correct |
105 |
Correct |
322 ms |
99124 KB |
Output is correct |
106 |
Correct |
380 ms |
99512 KB |
Output is correct |
107 |
Correct |
319 ms |
99112 KB |
Output is correct |
108 |
Correct |
276 ms |
111388 KB |
Output is correct |
109 |
Correct |
301 ms |
111152 KB |
Output is correct |
110 |
Correct |
238 ms |
92544 KB |
Output is correct |
111 |
Correct |
241 ms |
92720 KB |
Output is correct |
112 |
Correct |
335 ms |
92036 KB |
Output is correct |
113 |
Correct |
338 ms |
92284 KB |
Output is correct |