oj.uz

답안 #535104

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
535104 2022-03-09T12:08:33 Z new_acc Valley (BOI19_valley) C++14
100 / 100
 354 ms 46948 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=1e5+10;
const ll INF=1e18;
ll dp[N],g[N];
ll odl[N];
int jump[N][20],dep[N];
bitset<N>sk;
vector<pair<int,int> > zap[N];
ll res[N],mini[N][20];
vector<pair<pair<int,int>,int> > graf[N];
void dfs(int v,int o,ll xd){
	odl[v]=xd;
	if(sk[v]) dp[v]=0;
	else dp[v]=INF;
	for(auto [x,num]:graf[v]){
		int u=x.fi,c=x.se;
		if(o==u) continue;
		dep[u]=dep[v]+1;
		dfs(u,v,xd+(ll)c);
		dp[v]=min(dp[u]+(ll)c,dp[v]);
	}
}
ll zmini(int v,int d){
	ll res=(dp[v]==INF?INF:dp[v]-odl[v]);
	for(int i=18;i>=0;i--)
		if(dep[jump[v][i]]>=d) res=min(res,mini[v][i]),v=jump[v][i];
	return res;
}
void dfs2(int v,int o){
	jump[v][0]=o,mini[v][0]=min((dp[v]==INF?INF:dp[v]-odl[v]),(dp[o]==INF?INF:dp[o]-odl[o]));
	for(int i=1;i<=18;i++) jump[v][i]=jump[jump[v][i-1]][i-1],mini[v][i]=min(mini[v][i-1],mini[jump[v][i-1]][i-1]);
	for(auto [x,num]:graf[v]){
		int u=x.fi,c=x.se;
		if(o==u) continue;
		g[num]=dep[u];
		dfs2(u,v);
		g[num]=-1;
	}
	for(auto [num,i]:zap[v]){
		if(g[num]==-1) res[i]=-11;
		else{
			ll pom=zmini(v,g[num]);
			if(pom==INF) res[i]=-1;
			else res[i]=pom+odl[v];
		}
	}
}
void solve(){
	int n,s,q,e;
	cin>>n>>s>>q>>e;
	for(int i=1;i<n;i++){
		int a,b,c;
		cin>>a>>b>>c;
		graf[a].push_back({{b,c},i}),graf[b].push_back({{a,c},i});
	}
	for(int i=1;i<=s;i++){
		int a;
		cin>>a;
		sk[a]=1;
	}
	for(int i=1;i<=q;i++){
		int a,b;
		cin>>b>>a;
		zap[a].push_back({b,i});
	}
	for(int i=1;i<=n;i++) g[i]=-1;
	dfs(e,e,0);	
	dfs2(e,e);
	for(int i=1;i<=q;i++){
		if(res[i]==-11) cout<<"escaped\n";
		else{
			if(res[i]==-1) cout<<"oo\n";
			else cout<<res[i]<<"\n";
		}
	}
}
int main(){
	solve();
}

Compilation message

valley.cpp: In function 'void dfs(int, int, ll)':
valley.cpp:21:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   21 |  for(auto [x,num]:graf[v]){
      |           ^
valley.cpp: In function 'void dfs2(int, int)':
valley.cpp:38:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   38 |  for(auto [x,num]:graf[v]){
      |           ^
valley.cpp:39:14: warning: unused variable 'c' [-Wunused-variable]
   39 |   int u=x.fi,c=x.se;
      |              ^
valley.cpp:45:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   45 |  for(auto [num,i]:zap[v]){
      |           ^

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5324 KB Output is correct
2 Correct 7 ms 5324 KB Output is correct
3 Correct 10 ms 5404 KB Output is correct
4 Correct 11 ms 5336 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5324 KB Output is correct
2 Correct 7 ms 5324 KB Output is correct
3 Correct 10 ms 5404 KB Output is correct
4 Correct 11 ms 5336 KB Output is correct
5 Correct 6 ms 5324 KB Output is correct
6 Correct 5 ms 5324 KB Output is correct
7 Correct 7 ms 5324 KB Output is correct
8 Correct 5 ms 5324 KB Output is correct
9 Correct 5 ms 5324 KB Output is correct
10 Correct 5 ms 5324 KB Output is correct
11 Correct 5 ms 5404 KB Output is correct
12 Correct 5 ms 5324 KB Output is correct
13 Correct 5 ms 5324 KB Output is correct
14 Correct 4 ms 5324 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 293 ms 39236 KB Output is correct
2 Correct 273 ms 38832 KB Output is correct
3 Correct 283 ms 38684 KB Output is correct
4 Correct 354 ms 40740 KB Output is correct
5 Correct 293 ms 39956 KB Output is correct
6 Correct 333 ms 42308 KB Output is correct

Subtask #4
41.0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5324 KB Output is correct
2 Correct 7 ms 5324 KB Output is correct
3 Correct 10 ms 5404 KB Output is correct
4 Correct 11 ms 5336 KB Output is correct
5 Correct 6 ms 5324 KB Output is correct
6 Correct 5 ms 5324 KB Output is correct
7 Correct 7 ms 5324 KB Output is correct
8 Correct 5 ms 5324 KB Output is correct
9 Correct 5 ms 5324 KB Output is correct
10 Correct 5 ms 5324 KB Output is correct
11 Correct 5 ms 5404 KB Output is correct
12 Correct 5 ms 5324 KB Output is correct
13 Correct 5 ms 5324 KB Output is correct
14 Correct 4 ms 5324 KB Output is correct
15 Correct 293 ms 39236 KB Output is correct
16 Correct 273 ms 38832 KB Output is correct
17 Correct 283 ms 38684 KB Output is correct
18 Correct 354 ms 40740 KB Output is correct
19 Correct 293 ms 39956 KB Output is correct
20 Correct 333 ms 42308 KB Output is correct
21 Correct 238 ms 42556 KB Output is correct
22 Correct 262 ms 42200 KB Output is correct
23 Correct 257 ms 41960 KB Output is correct
24 Correct 343 ms 44336 KB Output is correct
25 Correct 282 ms 46948 KB Output is correct
26 Correct 267 ms 42564 KB Output is correct
27 Correct 251 ms 42104 KB Output is correct
28 Correct 309 ms 41880 KB Output is correct
29 Correct 313 ms 43512 KB Output is correct
30 Correct 335 ms 44544 KB Output is correct
31 Correct 247 ms 42612 KB Output is correct
32 Correct 282 ms 42308 KB Output is correct
33 Correct 256 ms 42132 KB Output is correct
34 Correct 311 ms 44264 KB Output is correct
35 Correct 289 ms 46812 KB Output is correct
36 Correct 289 ms 44328 KB Output is correct