제출 #1115815

#제출 시각아이디문제언어결과실행 시간메모리
1115815vjudge1Railway (BOI17_railway)C++17
100 / 100
169 ms29884 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pll pair<long long, long long> #define pb push_back #define F first #define S second #define all(x) (x).begin(), (x).end() const ll N = 2e5 + 100; const ll inf = 1e18; const ll mod = 1e9 + 7; const ll block = 450; struct Fen{ ll n; vector<ll>bit1, bit2; void init(ll _n){ n = _n; bit1.resize(_n + 10), bit2.resize(_n + 10); }; void updatePoint(vector<ll>& b, int u, ll v) { int idx = u; while (idx <= n) { b[idx] = (b[idx] + v); idx += (idx & (-idx)); } } void updateRange(int l, int r, ll v) { updatePoint(bit1, l, ((n - l + 1) * v)); updatePoint(bit1, r + 1, (-(n - r) * v)); updatePoint(bit2, l, v); updatePoint(bit2, r + 1, -v); } ll getSum(vector<ll>& b, ll u) { ll idx = u, ans = 0; while (idx > 0) { ans = (ans + b[idx]); idx -= (idx & (-idx)); } return ans; } ll prefixSum(ll u) { ll x = (getSum(bit1, u) - (getSum(bit2, u) * (n - u))); return x; } ll rangeSum(int l, int r) { ll x = (prefixSum(r) - prefixSum(l - 1)); return x; } } ft; ll n,m,timer = 0,k; ll sz[N], heavy[N], tin[N], head[N], p[N]; vector<pll>adj[N]; ll id[N]; void dfs(ll u, ll par){ sz[u] = 1; for(auto x : adj[u]){ ll v = x.F, i = x.S; if(v == par) continue; dfs(v, u); p[v] = u; id[v] = i; sz[u] += sz[v]; if(sz[v] > sz[heavy[u]]) heavy[u] = v; } } void HLD(ll u, ll h){ head[u] = h; tin[u] = ++timer; if(heavy[u]) HLD(heavy[u], h); for(auto x : adj[u]){ ll v = x.F; if(v != p[u] && v != heavy[u]) HLD(v, v); } } ll upd(ll a, ll b){ ll res = 0; for(; head[a] != head[b]; b = p[head[b]]){ if(tin[a] > tin[b]) swap(a, b); ft.updateRange(tin[head[b]], tin[b], 1); } if(tin[a] > tin[b]) swap(a, b); ft.updateRange(tin[a], tin[b], 1); ft.updateRange(tin[a], tin[a], -1); return res; } void to_thic_cau(){ cin >> n >> m >> k; for(int i = 1; i <= n - 1;i++){ ll u,v; cin >> u >> v; adj[u].pb({v, i}); adj[v].pb({u, i}); } dfs(1, 0); HLD(1, 0); ft.init(n); for(int i = 1; i <= m;i++){ vector<ll>vec; ll sz; cin >> sz; for(int j = 1; j <= sz;j++){ ll x; cin >> x; vec.pb(x); } sort(all(vec), [&](const ll &a, const ll &b){ return tin[a] < tin[b]; }); for(int i = 1; i < vec.size();i++) upd(vec[i-1], vec[i]); upd(vec[0], vec.back()); } vector<ll>ans; for(int i = 2; i <= n;i++){ if(ft.rangeSum(tin[i], tin[i]) >= 2 * k){ ans.pb(id[i]); } } sort(all(ans)); cout << ans.size() << "\n"; for(auto x : ans) cout << x << ' '; cout << "\n"; } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); ll tc = 1; //cin >> tc; while(tc--) to_thic_cau(); }

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

railway.cpp: In function 'void to_thic_cau()':
railway.cpp:106:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |   for(int i = 1; i < vec.size();i++) upd(vec[i-1], vec[i]);
      |                  ~~^~~~~~~~~~~~
#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...