제출 #966145

#제출 시각아이디문제언어결과실행 시간메모리
966145oblantisRailway (BOI17_railway)C++17
36 / 100
76 ms26576 KiB
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") //#pragma GCC optimize("O3,unroll-loops") #include <bits/stdc++.h> #define all(v) v.begin(), v.end() #define pb push_back #define ss second #define ff first #define vt vector #define uid(a, b) uniform_int_distribution<int>(a, b)(mt) using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int inf = 2e9; const int mod = 1e9+7; const int maxn = 1e5; mt19937 mt(chrono::steady_clock::now().time_since_epoch().count()); vt<int> g[maxn]; int in[maxn], up[maxn][20], dp[maxn], cnt, p[maxn]; void dfs(int v){ in[v] = cnt++; for(auto i : g[v]){ if(i == up[v][0])continue; up[i][0] = v, dp[i] = dp[v] + 1; for(int j = 1; j < 20; j++)up[i][j] = up[up[i][j - 1]][j - 1]; dfs(i); } } bool cmp(int x, int y){ return in[x] < in[y]; } void checkup(int v){ for(auto i : g[v]){ if(i == up[v][0])continue; checkup(i); p[v] += p[i]; } } int lca(int x, int y){ if(dp[x] > dp[y])swap(x, y); int k = dp[y] - dp[x], j = 0; while(k){ if(k & 1){ y = up[y][j]; } k >>= 1, j++; } if(y == x)return x; for(int j = 19; j >= 0; j--){ if(up[x][j] != up[y][j]){ x = up[x][j], y = up[y][j]; } } return up[x][0]; } void solve() { int n, m, k; cin >> n >> m >> k; int u[n - 1], v[n - 1]; for(int i = 0; i < n - 1; i++){ cin >> u[i] >> v[i]; --u[i], --v[i]; g[u[i]].pb(v[i]), g[v[i]].pb(u[i]); } dfs(0); for(int i = 0; i < m; i++){ int sz; cin >> sz; int c[sz]; for(int j = 0; j < sz; j++){ cin >> c[j]; --c[j]; } sort(c, c + sz, cmp); p[c[0]]++; p[lca(c[0], c[1])]--; for(int j = 1; j < sz; j++){ p[c[j]]++; p[lca(c[j], c[j - 1])]--; } } checkup(0); vt<int> ans; for(int i = 0; i < n - 1; i++){ if(dp[u[i]] > dp[v[i]])swap(u[i], v[i]); if(p[v[i]] >= k){ ans.pb(i + 1); } } cout << ans.size() << '\n'; for(auto i : ans)cout << i << ' '; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int times = 1; //cin >> times; for(int i = 1; i <= times; i++) { solve(); } return 0; }
#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...