Submission #1202653

#TimeUsernameProblemLanguageResultExecution timeMemory
1202653pcheloveksRailway (BOI17_railway)C++20
0 / 100
46 ms22916 KiB
#pragma GCC optimize("Ofast") #pragma GCC optimize ("unroll-loops") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4") //#pragma GCC target("bmi,bmi2,popcnt,lzcnt") //Andrew Holod will NOT win IOI 2025 //Andrew Holod did not qualify to IOI 2025)))))))))) //Anton is nigga #include <iostream> #include <vector> #include <string> #include <map> #include <set> #include <cmath> #include <fstream> #include <climits> #include <queue> #include <algorithm> #include <stdint.h> #include <stack> #include <iomanip> #include <unordered_set> #include <unordered_map> #include <bitset> #include <cstring> // Для memset using namespace std; typedef long long ll; typedef long double ld; typedef std::pair <ll, ll> pii; typedef std::pair <ld, ld> pdd; const ll DIM = 100007; const ll MXMASK = (1 << 20); const ll INF = 1e18; const ll mod = 1000000007; const ld eps = 0.00000000001; const ld gr = (sqrt(5) + 1) / 2; const ll offset = 10000; const ll Bits = 20; const char endL = '\n'; const ll dx[4] = { 1, 0, -1, 0 }; const ll dy[4] = { 0, 1, 0, -1 }; FILE* stream; int n, m, k; vector < pair < int, int > > v[DIM]; int timer; int euler[DIM], tin[DIM], tout[DIM], heavy[DIM], weight[DIM], depth[DIM]; vector < int > colors[DIM]; vector < int > res; void precount(int val, int prev, int dep) { tin[val] = ++timer; euler[timer] = val; depth[val] = dep; weight[val] = 1; for (auto e : v[val]) { int to = e.first; if (to == prev) continue; precount(to, val, dep + 1); weight[val] += weight[to]; } tout[val] = timer; } int cnt[DIM], fullColor[DIM]; int ans; void add(int col) { if (cnt[col] == 0) ans++; cnt[col]++; if (cnt[col] == fullColor[col]) ans--; } void del(int col) { if (cnt[col] == fullColor[col]) ans++; cnt[col]--; if (cnt[col] == 0) ans--; } void solve(int val, int prev, bool heavyStat) { int heavy = 0, heavyE = 0; for (auto e : v[val]) { int to = e.first, num = e.second; if (num == prev) continue; if (weight[to] > weight[heavy]) { heavy = to; heavyE = num; } } for (auto e : v[val]) { int to = e.first, num = e.second; if (to != heavy && num != prev) { solve(to, num, false); } } if (heavy != 0) { solve(heavy, heavyE, true); } for (auto e : v[val]) { int to = e.first, num = e.second; if (to != heavy && num != prev) { for (int i = tin[to]; i <= tout[to]; i++) { for (auto x : colors[euler[i]]) { add(x); } } } } for (auto x : colors[val]) { add(x); } if (ans >= k && prev != -1) res.push_back(prev); if (!heavyStat) { for (int i = tin[val]; i <= tout[val]; i++) { for (auto x : colors[euler[i]]) { del(x); } } } } int main() { std::ios_base::sync_with_stdio(0); std::cin.tie(0); std::cout.tie(0); //freopen_s(&stream, "input.txt", "r", stdin); //freopen_s(&stream, "output.txt", "w", stdout); cin >> n >> m >> k; for (int i = 1; i < n; i++) { int v1, v2; cin >> v1 >> v2; v[v1].push_back({ v2, i }); v[v2].push_back({ v1, i }); } precount(1, 1, 1); for (int i = 1; i <= m; i++) { int x; cin >> fullColor[i]; for (int j = 1; j <= fullColor[i]; j++) { cin >> x; colors[x].push_back(i); } } solve(1, -1, true); cout << res.size() << endl; for (auto x : res) cout << x << " "; 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...