제출 #1098629

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1098629		flyingkite	Railway (BOI17_railway)	C++17	100 / 100	176 ms	27380 KiB

railway

#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]);
      |                  ~~^~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 7 / 7
• Subtask 4: 29 / 29
• Subtask 5: 16 / 16
• Subtask 6: 25 / 25