제출 #654887

#제출 시각아이디문제언어결과실행 시간메모리
654887rafatoaRailway (BOI17_railway)C++17
0 / 100
2 ms596 KiB
#include <bits/stdc++.h> using namespace std; typedef long long int ll; typedef long double ld; #pragma GCC optimize ("Ofast") #define double ld #define F first #define S second #define vi vector<int> #define vvi vector<vi> #define pi pair<int, int> #define vpi vector<pi> #define vb vector<bool> #define vvb vector<vb> #define pb push_back #define ppb pop_back #define read(a) for(auto &x:a) cin >> x; #define print(a) for(auto x:a) cout << x << " "; cout << "\n"; #define rs resize #define as assign #define vc vector<char> #define vvc vector<vc> #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define MP make_pair #define int long long const int INF = 4e18; const int inf = 2e9; struct segTree{ int N; vi tree; segTree(int n){ N = (1LL<<(int)ceil(log2(n))); tree = vi(2*N, 0); } void update(int k, int val){ k += N; tree[k] += val; for(k /= 2; k >= 1; k /= 2) tree[k] = tree[2*k]+tree[2*k+1]; } int query(int a, int b){ a += N, b += N; int ans = 0; while(a <= b){ if(a%2 == 1) ans += tree[a++]; if(b%2 == 0) ans += tree[b--]; a /= 2, b /= 2; } return ans; } }; void solve(){ int n, m, k; cin >> n >> m >> k; vector<vpi> adj(n+1); vvi up(n+1, vi(21)); for(int i=0; i<n-1; i++){ int u, v; cin >> u >> v; adj[u].pb({v, i+1}); adj[v].pb({u, i+1}); } vi in(n+1), out(n+1), d(n+1), edpar(n+1); int time = 0; function<void(int)> dfs = [&](int s){ in[s] = time++; for(auto [u, ed]:adj[s]) if(u != up[s][0]){ up[u][0] = s; d[u] = d[s]+1; edpar[u] = ed; dfs(u); } out[s] = time++; }; dfs(1); for(int j=1; j<=20; j++) for(int i=1; i<=n; i++) up[i][j] = up[up[i][j-1]][j-1]; function<int(int, int)> lca = [&](int a, int b){ if(d[a] > d[b]) swap(a, b); for(int j=20; j>=0; j--) if((d[b]-d[a])&(1LL<<j)) b = up[b][j]; for(int j=20; j>=0; j--) if(up[a][j] != up[b][j]) a = up[a][j], b = up[b][j]; if(a == b) return a; return up[a][0]; }; segTree st(2*n); while(m--){ int sz; cin >> sz; vi nod(sz); read(nod); sort(all(nod), [&](int a, int b){ return (in[a] < in[b]); }); nod.pb(nod[0]); for(int i=0; i<sz; i++){ int p = lca(nod[i], nod[i+1]); st.update(in[p], -2); st.update(in[nod[i]], 1); st.update(in[nod[i+1]], 1); } } vi ans; for(int i=2; i<=n; i++) if(st.query(in[i], out[i]) >= 2*k) ans.pb(edpar[i]); cout << ans.size() << "\n"; print(ans); } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif solve(); return 0; } /*stolen stuff you should look for * int overflow, array bounds * special cases (n=1?) * READ CONSTRAINTS * do smth instead of nothing and stay organized * WRITE STUFF DOWN * DON'T GET STUCK ON ONE APPROACH */

컴파일 시 표준 에러 (stderr) 메시지

railway.cpp: In function 'int main()':
railway.cpp:134:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  134 |         freopen("in.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
railway.cpp:135:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  135 |         freopen("out.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#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...