제출 #1253953

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1253953		_rain_	Valley (BOI19_valley)	C++20	100 / 100	162 ms	47984 KiB

valley

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define int long long

#define ii pair<int,int>
#define BIT(mask,x) (((mask)>>(x))&(1))
#define MASK(x) ((LL)(1)<<(x))
#define FOR(i,a,b) for(int i = (a),_b=(b); i<=_b;++i)
#define FORD(i,a,b) for(int i =(a),_b=(b);i>=_b;--i)

template<class X,class Y>
	bool maximize(X &x,Y y){
		if (x<y) return x=y,true; else return false;
	}
template<class X,class Y>
	bool minimize(X &x,Y y){
		if (x>y) return x=y,true; else return false;
	}
template<class T>
	void compress(vector<T>&data){
		sort(data.begin() , data.end());
		data.resize(unique(data.begin() , data.end()) - data.begin());
	}

mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
	LL Rand(LL l,LL r){
		return uniform_int_distribution<LL>(l,r)(rng);
	}
	
const int N = (int)1e5;
const LL inf = (LL)1e18;
const int MAXLOG = (int)16;
	int par[N+2][MAXLOG+2] = {} , h[N+2] = {};
	int sta[N+2] = {} , fin[N+2] = {} , time_dfs = 0;
	int u[N+2] , v[N+2] , w[N+2] ;
	LL dist[N+2] = {} , f[N+2] = {} , cost[N+2] = {} , up[N+2][MAXLOG+2] = {};
	vector<pair<int,int>>ke[N+2] ;
	
	int n , s , q , es;
	
		void add_canh(int u,int v,int w){
			ke[u].push_back({v,w}) , 
			ke[v].push_back({u,w});
			return;
		}
		
	void dfs(int u,int p){
		sta[u] = ++time_dfs;
		h[u] = h[p] + 1;
		for(auto&v:ke[u]){
			if (v.first==p) continue;
			dist[v.first] = dist[u] + v.second;
			dfs(v.first , u);
			minimize(f[u] , f[v.first] + v.second);
		}
		cost[u] = f[u] - dist[u];
		for(auto&v:ke[u]){
			if (v.first==p) continue;
			up[v.first][0] = cost[u];
			par[v.first][0] = u;
		}
		fin[u] = time_dfs;
		return;
	}
		
	bool is_par(int u,int lca){
		return sta[lca] <= sta[u] && sta[u] <= fin[lca];
	}
		
	LL Get_cost(int u,int lca){
		LL res = min(cost[u] , cost[lca]);
		for(int i = MAXLOG; i >= 0; --i){
			if (h[par[u][i]] >= h[lca]) {
				minimize(res , up[u][i]);
				u = par[u][i];
			}
		}
		return res;
	}

int32_t main(){
	
	ios::sync_with_stdio(false);
	cin.tie(0) ; cout.tie(0) ;
	#define name "main"
		if (fopen(name".inp","r")){
			freopen(name".inp","r",stdin);
			freopen(name".out","w",stdout);
		}
		
		cin>>n>>s>>q>>es;
		FOR(i,1,n) f[i] = inf;
		FOR(i,1,n-1) {
			cin>>u[i]>>v[i]>>w[i];
			add_canh(u[i],v[i],w[i]);
		}
		FOR(i,1,s) {
			int v; cin>>v;
			f[v] = 0;
		}
		dfs(es,0);
		FOR(j,1,MAXLOG){
			FOR(i,1,n) par[i][j] = par[par[i][j-1]][j-1];
			FOR(i,1,n) up[i][j] = min(up[i][j-1] , up[par[i][j-1]][j-1]);
		}
		while(q--){
			int id,r; cin>>id>>r;
			int x = u[id] , y = v[id];
			if (h[x] > h[y]) swap(x,y);
			if (is_par(r , y)){
				LL ans = dist[r] + Get_cost(r , y);
				if (ans >= inf) cout<<"oo"; else cout<<ans;
				cout<<'\n';
			}
			else cout<<"escaped\n";
		}
	return 0;
}

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

valley.cpp: In function 'int32_t main()':
valley.cpp:88:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |                         freopen(name".inp","r",stdin);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
valley.cpp:89:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |                         freopen(name".out","w",stdout);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 27 / 27
• Subtask 3: 23 / 23
• Subtask 4: 41 / 41