oj.uz

답안 #712815

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
712815 2023-03-20T07:59:26 Z TimDee Valley (BOI19_valley) C++17
100 / 100
 194 ms 29196 KB 
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2,popcnt")

#define int long long
#define forn(i,n) for(size_t i=0;i<n;++i)
#define pb push_back
#define all(x)  x.begin(),x.end()
#define pi pair<int,int>
#define f first
#define s second

const int inf=1e18;
const int N=1e5;
int sz[N],d[N],par[N],top[N],ind[N],rind[N];
int dist[N],dp[N];
int shop[N];

int z=0;
vector<pi> adj[N];
pi e[N];
int W[N];

struct sgt {
	vector<int> t;
	int sz;
	sgt(int n) {
		sz=1; 
		while(sz<n) sz<<=1; 
		t.assign(2*sz,inf);
	}
	void upd(int v, int l, int r, int i) {
		if (r-l==1) return;
		int m=(l+r)>>1;
		if (i<m) upd(2*v+1,l,m,i);
		else upd(2*v+2,m,r,i);
		t[v]=min(t[2*v+1],t[2*v+2]);
	}
	void set(int i, int x) {
		t[sz-1+i]=x;
		upd(0,0,sz,i);
	}
	int q(int v, int l, int r, int lx, int rx) {
		if (rx<=l || r<=lx) return inf;
		if (lx<=l && r<=rx) return t[v];
		int m=(l+r)>>1;
		int lq=q(2*v+1,l,m,lx,rx);
		int rq=q(2*v+2,m,r,lx,rx);
		return min(lq,rq);
	}
	int q(int l, int r) {
		if (l>=r) return inf;
		return q(0,0,sz,l,r);
	}
};
sgt st(N);

void dfs(int u, int p) {
	sz[u]=1;
	dp[u]=shop[u]?0:inf;
	for(auto&e:adj[u]) {
		int v=e.f, w=e.s;
		if (v==p) continue;
		d[v]=d[u]+1;
		dist[v]=dist[u]+w;
		par[v]=u;
		dfs(v,u);
		sz[u]+=sz[v];
		dp[u]=min(dp[v]+w,dp[u]);
	}
}
void dfs(int u, int p, int t) {
	top[u]=t;
	rind[z]=u;
	ind[u]=z++;
	st.set(ind[u],(dp[u]==inf)?inf:(dp[u]-dist[u]));
	int mx=-1;
	for(auto&e:adj[u]) {
		int v=e.f, w=e.s;
		if (v==p) continue;
		if (mx==-1) mx=v;
		if (sz[v]>sz[mx]) mx=v;
	}
	if (mx==-1) return;
	dfs(mx,u,t);
	for(auto&e:adj[u]) {
		int v=e.f, w=e.s;
		if (v==p || v==mx) continue;
		dfs(v,u,v);
	}
}

int lca(int u, int v) {
	while (top[u]!=top[v]) {
		if (d[top[u]]<d[top[v]]) swap(u,v);
		u=par[top[u]];
	}
	return (d[u]<d[v])?u:v;
}

int query(int u, int v) {
	int ret=inf;
	while (top[u]!=top[v]) {
		int q=st.q(ind[top[u]],ind[u]+1);
		ret=min(ret,q);
		u=par[top[u]];
	}
	int q=st.q(ind[v],ind[u]+1);
	return min(ret,q);
}

void solve() {

	int n,s,q,E; cin>>n>>s>>q>>E; --E;
	forn(i,n-1) {
		int u,v,w; cin>>u>>v>>w; --u,--v;
		adj[u].pb({v,w});
		adj[v].pb({u,w});
		e[i]={u,v};
		W[i]=w;
	}
	forn(i,s) {
		int u; cin>>u; --u; shop[u]=1;
	}
	dfs(E,-1);
	dfs(E,-1,E);
	//forn(i,n) cout<<dp[i]<<' '; cout<<'\n';
	//forn(i,n) cout<<ind[i]<<' '; cout<<'\n';
	//forn(i,n) forn(j,n) if (j>=i) cout<<i<<' '<<j<<' '<<st.q(i,j+1)<<'\n';
	while (q--) {
		int i, x; cin>>i>>x; --i, --x;
		int u=e[i].f, v=e[i].s;
		if (par[u]==v) swap(u,v);
		if (lca(x,v)!=v) {
			cout<<"escaped\n";
			continue;
		}
		int z=query(x,v);
		if (z==inf) cout<<"oo\n";
		else cout<<z+dist[x]<<'\n';
	}

}
 
int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t=1;
	//cin >> t;
	while (t--) solve();
	return 0;
}

Compilation message

valley.cpp: In function 'void dfs(long long int, long long int, long long int)':
valley.cpp:82:14: warning: unused variable 'w' [-Wunused-variable]
   82 |   int v=e.f, w=e.s;
      |              ^
valley.cpp:90:14: warning: unused variable 'w' [-Wunused-variable]
   90 |   int v=e.f, w=e.s;
      |              ^
valley.cpp: In function 'void solve()':
valley.cpp:9:35: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
    9 | #define forn(i,n) for(size_t i=0;i<n;++i)
......
  118 |  forn(i,n-1) {
      |       ~~~~~                        
valley.cpp:118:2: note: in expansion of macro 'forn'
  118 |  forn(i,n-1) {
      |  ^~~~
valley.cpp:9:35: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
    9 | #define forn(i,n) for(size_t i=0;i<n;++i)
      |                                   ^
valley.cpp:125:2: note: in expansion of macro 'forn'
  125 |  forn(i,s) {
      |  ^~~~

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 4892 KB Output is correct
2 Correct 6 ms 4844 KB Output is correct
3 Correct 5 ms 4896 KB Output is correct
4 Correct 5 ms 4820 KB Output is correct

Subtask #2
27.0 / 27.0

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

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 141 ms 23764 KB Output is correct
2 Correct 153 ms 23568 KB Output is correct
3 Correct 159 ms 23756 KB Output is correct
4 Correct 190 ms 26068 KB Output is correct
5 Correct 149 ms 26136 KB Output is correct
6 Correct 157 ms 28620 KB Output is correct

Subtask #4
41.0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 4892 KB Output is correct
2 Correct 6 ms 4844 KB Output is correct
3 Correct 5 ms 4896 KB Output is correct
4 Correct 5 ms 4820 KB Output is correct
5 Correct 4 ms 4892 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4892 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 4 ms 4892 KB Output is correct
10 Correct 4 ms 4948 KB Output is correct
11 Correct 4 ms 4948 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct
15 Correct 141 ms 23764 KB Output is correct
16 Correct 153 ms 23568 KB Output is correct
17 Correct 159 ms 23756 KB Output is correct
18 Correct 190 ms 26068 KB Output is correct
19 Correct 149 ms 26136 KB Output is correct
20 Correct 157 ms 28620 KB Output is correct
21 Correct 125 ms 22392 KB Output is correct
22 Correct 143 ms 22304 KB Output is correct
23 Correct 136 ms 22448 KB Output is correct
24 Correct 161 ms 24944 KB Output is correct
25 Correct 154 ms 28452 KB Output is correct
26 Correct 125 ms 22716 KB Output is correct
27 Correct 173 ms 22508 KB Output is correct
28 Correct 159 ms 22964 KB Output is correct
29 Correct 171 ms 24524 KB Output is correct
30 Correct 166 ms 26316 KB Output is correct
31 Correct 124 ms 23244 KB Output is correct
32 Correct 148 ms 23080 KB Output is correct
33 Correct 147 ms 23368 KB Output is correct
34 Correct 184 ms 25688 KB Output is correct
35 Correct 194 ms 29196 KB Output is correct
36 Correct 157 ms 25688 KB Output is correct