제출 #917669

#제출 시각아이디문제언어결과실행 시간메모리
917669trMatherzRailway (BOI17_railway)C++17
36 / 100
186 ms36996 KiB
#include <iostream> //cin, cout /* #include <fstream> std::ifstream cin ("ex.in"); std::ofstream cout ("ex.out"); */ // includes #include <cmath> #include <set> #include <map> #include <queue> #include <string> #include <vector> #include <array> #include <algorithm> #include <numeric> #include <iomanip> #include <unordered_set> #include <stack> #include <ext/pb_ds/assoc_container.hpp> #include <random> #include <chrono> //usings using namespace std; using namespace __gnu_pbds; // misc #define ll long long #define pb push_back #define pq priority_queue #define ub upper_bound #define lb lower_bound template<typename T, typename U> bool emin(T &a, const U &b){ return b < a ? a = b, true : false; } template<typename T, typename U> bool emax(T &a, const U &b){ return b > a ? a = b, true : false; } typedef uint64_t hash_t; // vectors #define vi vector<int> #define vvi vector<vi> #define vvvi vector<vvi> #define vpii vector<pair<int, int>> #define vvpii vector<vector<pair<int, int>>> #define vppipi vector<pair<int, pair<int, int>>> #define vl vector<ll> #define vvl vector<vl> #define vvvl vector<vvl> #define vpll vector<pair<ll, ll>> #define vb vector<bool> #define vvb vector<vb> #define vs vector<string> #define sz(x) (int)x.size() #define rz resize #define all(x) x.begin(), x.end() // pairs #define pii pair<int, int> #define pll pair<ll, ll> #define mp make_pair #define f first #define s second // sets #define si set<int> #define sl set<ll> #define ss set<string> #define in insert template <class T> using iset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; // maps #define mii map<int, int> #define mll map<ll, ll> // loops #define FR(x, z, y) for (int x = z; x < y; x++) #define FRE(x, z, y) FR(x, z, y + 1) #define F(x, y) FR(x, 0, y) #define FE(x, y) F(x, y + 1) #define A(x, y) for(auto &x : y) int n, m, k; map<pii, int> w; vvi a, dp; vi v, d; vi ans; void dfs(int x){ FR(i, 1, 18) dp[x][i] = dp[dp[x][i - 1]][i - 1]; A(u, a[x]) if(u != dp[x][0]) d[u] = d[dp[u][0] = x] + 1, dfs(u); } int jump(int x, int v){ F(i, 18) if((1 << i) & v) x = dp[x][i]; return x; } int lca(int x, int y){ if(d[y] > d[x]) swap(x, y); x = jump(x, d[x] - d[y]); if(x == y) return x; for(int i = 17; i >= 0; i--) if(dp[x][i] != dp[y][i]) x = dp[x][i], y = dp[y][i]; return dp[x][0]; } int go(int x){ int cur = 0; A(u, a[x]) if(u != dp[x][0]) cur += go(u); cur += v[x]; if(cur >= k && dp[x][0] != x) ans.pb(w[{min(dp[x][0], x), max(dp[x][0], x)}]); return cur; } int main(){ cin >> n >> m >> k; a = vvi(n); dp = vvi(n, vi(18, 0)); v = d = vi(n, 0); F(i, n - 1){ int x, y; cin >> x >> y; x--; y--; if(y < x) swap(x, y); w[{x, y}] = i; a[x].pb(y); a[y].pb(x); } dfs(0); while(m--){ int x; cin >> x; vi temp(x); A(u, temp) cin >> u, u--; int p = -1; A(u, temp){ if(p != -1){ v[u]++; v[p]++; v[lca(u, p)] -= 2; } p = u; } } go(0); sort(all(ans)); cout << sz(ans) << endl; A(u, ans) cout << u + 1 << " "; }
#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...