제출 #1115808

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1115808		vjudge1	Railway (BOI17_railway)	C++17	100 / 100	259 ms	37384 KiB

railway

#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2")
#include<bits/stdc++.h>
#define all(x) (x).begin() , (x).end()
#define pll pair<long long, long long>
#define fi first 
#define se second 
#define bit(i,j) ((j >> i) & 1) 
#define lowbit(x) (x & (-x))
#define sigma main
using namespace std;

const long long inf = 1e18+1; 
const int mod = 998244353; 
const int MAXN = 2e5+100;

#define int long long

template<class T , class U>
struct segment_tree{
	T t[4 * MAXN];
	U d[4 * MAXN];

	const T Ti = 0;
	const U Ui = 0;
	T combine(T a, T b) {
		return a + b;
	}
	void apply(T &a, U b, int l , int r){
		a += b;
	}
	void lazy(U &a , U b){
		a += b;
	}
	segment_tree(){
		for(int i = 0 ; i < 4 * MAXN ; i++) d[i] = Ui;
	}

	void build(int id , int l , int r){
		if(l == r) {
			t[id] = Ti; return;
		}
		int mid = l + r >> 1;
		build(id<<1 , l , mid ) ; build(id<<1|1 , mid+1 , r );
		t[id] = combine(t[id<<1] , t[id<<1|1]);
	}
	void push(int id , int l , int r){
		if(l == r) return ;
		lazy(d[id<<1] , d[id]); lazy(d[id<<1|1] , d[id]);
		int mid = l + r >> 1;
		apply(t[id<<1] , d[id] , l , mid) ; apply(t[id<<1|1] , d[id] , mid+1 , r); 
		d[id] = Ui;
	}

	void update(int id , int l , int r , int x , int y , U val){
		push(id, l , r);
		if(l > y or r < x) return ;
		if(l >= x and r <= y){
			lazy(d[id] , val);
			apply(t[id] , val , l , r);
			return;
		}
		int mid = l + r >> 1;
		update(id<<1 , l , mid , x ,y , val) ; update(id<<1|1 , mid+1 , r , x , y , val);
		t[id] = combine(t[id<<1] , t[id<<1|1]);
	}

	T get(int id , int l , int r , int x , int y){
		push(id , l , r);	
		if(l > y or r < x) return Ti;
		if(l >= x and r <= y){
			return t[id];	
		}
		int mid = l + r >> 1;
		return combine(get(id<<1 , l , mid , x , y) , get(id<<1|1 , mid+1 ,r , x , y));
	}
};

segment_tree<int , int> T;
vector<int> adj[MAXN];

int nxt[MAXN] , par[MAXN] , h[MAXN];
int dfs(int u , int p){
	int sz = 1 , mx = 0;
	for(auto v : adj[u]){
		if(v == p) continue;
		par[v] = u;
		h[v] = h[u] + 1;
		int c = dfs(v , u);
		sz += c;
		if(c > mx){
			nxt[u] = v; mx = c;
		}
	}
	return sz;
}
 
int in[MAXN] , out[MAXN] , head[MAXN];
int Time = 0;
void hld(int u, int h){
	head[u] = h;
	in[u] = ++Time;
	if(nxt[u] != 0){
		hld(nxt[u] , h);
	}
	for(auto v : adj[u]){
		if(v == par[u] or v == nxt[u]) continue;
		hld(v , v);
	}
	out[u] = Time;
}

int lca(int u , int v){
	while(head[u] != head[v]){
		if(in[head[u]] > in[head[v]]){
			u = par[head[u]];
		}else{
			v = par[head[v]];
		}
	}
	if(h[u] > h[v]) return v;
	return u;
}

int n , m , k;
void upd(int u , int v){
	while(head[u] != head[v]){
		T.update(1 , 1 , n , in[head[u]] , in[u] , 1);
		u = par[head[u]];
	}
	T.update(1 , 1 , n , in[v] , in[u] , 1);
	T.update(1 , 1 , n , in[v] , in[v] , -1);
}
int32_t sigma(){
  	//freopen("COLOREDBALLS.inp", "r", stdin);
	//freopen("COLOREDBALLS.out", "w", stdout);
	ios_base::sync_with_stdio(0); cin.tie(0);

	int k; cin >> n >> m >> k;
	vector<pll> E(n);
	for(int i = 1; i < n ; i++){
		int a , b; cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
		E[i] = {a , b};
	}
	dfs(1 , 1); hld(1 , 1);
	for(int i = 1 ;i <= m ; i++){
		int s; cin >> s;
		vector<int> v;
		while(s--){
			int x; cin >> x; v.push_back(x);
		}
		sort(all(v) , [&](int a , int b){
			return in[a] < in[b];

		});
		for(int i = 0 ; i < v.size() ; i++){
			int j = (i + 1) % v.size();
			int p = lca(v[i] , v[j]);
			upd(v[i] , p); upd(v[j] , p);
		}
	}

	vector<int> ans;
	for(int i = 1 ; i < n ; i++){
		int u = E[i].fi , v = E[i].se;
		if(in[u] < in[v]) swap(u , v);
		if(T.get(1 , 1 , n , in[u] , in[u]) >= 2 * k) ans.push_back(i);
	}
	cout << ans.size() << "\n";
	for(auto x : ans) cout << x << " ";
	cout << endl;

	return 0;
}

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

railway.cpp: In function 'int32_t main()':
railway.cpp:158:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  158 |   for(int i = 0 ; i < v.size() ; i++){
      |                   ~~^~~~~~~~~~
railway.cpp: In instantiation of 'void segment_tree<T, U>::update(long long int, long long int, long long int, long long int, long long int, U) [with T = long long int; U = long long int]':
railway.cpp:128:47:   required from here
railway.cpp:63:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |   int mid = l + r >> 1;
      |             ~~^~~
railway.cpp: In instantiation of 'T segment_tree<T, U>::get(long long int, long long int, long long int, long long int, long long int) [with T = long long int; U = long long int]':
railway.cpp:169:37:   required from here
railway.cpp:74:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   74 |   int mid = l + r >> 1;
      |             ~~^~~
railway.cpp: In instantiation of 'void segment_tree<T, U>::push(long long int, long long int, long long int) [with T = long long int; U = long long int]':
railway.cpp:56:3:   required from 'void segment_tree<T, U>::update(long long int, long long int, long long int, long long int, long long int, U) [with T = long long int; U = long long int]'
railway.cpp:128:47:   required from here
railway.cpp:50:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |   int mid = l + r >> 1;
      |             ~~^~~

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