Submission #1248216

#TimeUsernameProblemLanguageResultExecution timeMemory
1248216MinbaevRailway (BOI17_railway)C++20
36 / 100
413 ms147216 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #pragma GCC target("avx,avx2,fma") #pragma GCC optimize("Ofast,unroll-loops") using namespace std; using namespace __gnu_pbds; #define pb push_back #define all(x) x.begin(),x.end() #define int long long #define ar array #define mrand(a, b) uniform_int_distribution<int>(a, b)(rng) template<class T>bool umax(T &a,T b){if(a<b){a=b;return true;}return false;} template<class T>bool umin(T &a,T b){if(b<a){a=b;return true;}return false;} template<class T> using ste = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); namespace FAST { template<typename T, typename F> istream &operator>>(istream &cin, pair<T, F> &p) { cin >> p.first >> p.second; return cin; } template<typename T, typename F> ostream &operator<<(ostream &cout, pair<T, F> &p) { cout << p.first << ' ' << p.second; return cout; } template<typename T> istream &operator>>(istream &cin, vector<T> &a) { for (T &i: a) cin >> i; return cin; } template<typename T> ostream &operator<<(ostream &cout, vector<T> &a) { for (T i: a) cout << i << ' '; return cout; } template<typename T> istream &operator>>(istream &cin, deque<T> &a) { for (T &i: a) cin >> i; return cin; } template<typename T> ostream &operator<<(ostream &cout, deque<T> &a) { for (T i: a) cout << i << ' '; return cout; } } using namespace FAST; const int inf = 1e17 + 7; const int mod = 1e9 + 7; const int N = 3e5 + 5; const int md = 998244353; int binpow(int a, int b, int m){ if(b == 0)return 1; if(b % 2 == 0){ int c = binpow(a,b/2,m); return (c*c)%m; } return (binpow(a,b-1,m)*a)%m; } int divi(int a, int b, int m){ return (a*(binpow(b,m-2, m)))%m; } struct Bit { vector<int> b, b2; int n; Bit(int n) { this->n = n + 1; b.assign(n + 1, 0); b2.assign(n+1, 0); } void add(vector<int>&b, int idx, int x){ while(idx <= n){ b[idx] += x; idx += idx & -idx; } } void update(int l, int r, int x){ add(b, l, x); add(b, r+1, -x); add(b2, l, x*(l-1)); add(b2, r+1, -x*r); } int sum(vector<int>&b, int idx){ int res = 0; while(idx > 0){ res += b[idx]; idx -= idx & -idx; } return res; } int pref(int idx){ return sum(b, idx) * idx - sum(b2, idx); } int get(int l, int r){ return pref(r) - pref(l-1); } }; int n,m,k; int timer; int op[N][21]; vector<int>g[N], tin(N), tout(N); vector<int>sz(N), baty(N); ste<int>s[N]; ste<int>s2[N]; map<ar<int,2>, int> res, ind; void dfs(int x, int pr){ op[x][0] = pr; for(int i = 1;i<=20;i++){ op[x][i] = op[op[x][i-1]][i-1]; } tin[x] = timer++; for(auto to:g[x]){ if(to == pr)continue; dfs(to, x); } tout[x] = timer++; } bool isbaty(int a, int b){ return (tin[a] < tin[b] && tout[b] < tout[a]); } int lca(int a, int b){ if(isbaty(a, b))return a; if(isbaty(b, a))return b; for(int i = 20;i>=0;i--){ if(!isbaty(op[a][i], b))a = op[a][i]; } return op[a][0]; } int find_baty(int x){ if(baty[x] == x)return x; return baty[x] = find_baty(baty[x]); } void unin(int a, int b){ a = find_baty(a); b = find_baty(b); if(a == b)return; if(s[a].size() < s[b].size())swap(a, b); baty[b] = a; for(auto to:s[b]){ s[a].insert(to); } } void ans(int x, int pr){ for(auto to:g[x]){ if(to == pr)continue; ans(to, x); unin(x, to); } int a = find_baty(x); // if(x == 3){ // for(auto to:s[a])cout << to << " "; // cout << "\n"; // for(auto to:s2[x])cout << to << " "; // cout << "\n"; // } for(auto to:s2[x]){ int in = s[a].order_of_key(to); if(0 <= in && in < s[a].size() && *s[a].find_by_order(in) == to){ s[a].erase(s[a].find_by_order(in)); } } res[{x, pr}] = s[a].size(); } void solve(){ cin >> n >> m >> k; for(int i = 1;i<=n;i++){ baty[i] = i; } for(int i = 2;i<=n;i++){ int a,b; cin >> a >> b; ind[{a, b}] = i-1; ind[{b, a}] = i-1; g[a].pb(b); g[b].pb(a); } dfs(1, 1); // cout << isbaty(3, 6) << "\n"; // cout << op[6][1] << "\n"; for(int i = 1;i<=m;i++){ int a; cin >> a; int last = -1; for(int j = 1;j<=a;j++){ int b; cin >> b; if(last > -1){ int u = lca(last, b); if(u != last) s[last].insert(i); if(u != b) s[b].insert(i); s2[u].insert(i); if(u != last && u != b)s2[u].insert(i); } last = b; } // cout << "\n"; } // for(auto to:s[3])cout << to << " "; // cout << "\n"; ans(1, -1); vector<int>opp; for(auto to:res){ if(to.second >= k){ if(ind[to.first] == 0)continue; opp.pb(ind[to.first]); } // cout << to.first[0] << " " << to.first[1] << " " << to.second << "\n"; } sort(all(opp)); cout << opp.size() << "\n"; cout << opp << "\n"; } /* */ signed main() { // freopen("seq.in", "r", stdin); // freopen("seq.out", "w", stdout); ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL); int tt=1; //cin >> tt; while(tt--)solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...