Submission #171033

#	Time	Username	Problem	Language	Result	Execution time	Memory
171033		dndhk	Valley (BOI19_valley)	C++14	100 / 100	609 ms	39896 KiB

valley

#include <bits/stdc++.h>

#define all(v) (v).begin(), (v).end()
#define sortv(v) sort(all(v))
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define pb push_back
#define FI first
#define SE second
#define lb lower_bound
#define ub upper_bound
#define mp make_pair
#define test 1
#define TEST if(test)

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

const int MOD = 1000000007; // 998244353
const int INF = 2e9;
const ll INFLL = 1e18;
const int MAX_N = 100000;

int N, S, Q, E;
struct Edge{
	int x, l, idx;
};
vector<Edge> gp[MAX_N+1];
bool chk[MAX_N+1];
ll dist[2][MAX_N+1];
int in[MAX_N+1], out[MAX_N+1], cnt, p[MAX_N+1], uidx[MAX_N+1];


struct SEG{
	struct NODE{
		int l, r;
		ll mn, lazy;
	};
	vector<NODE> seg;
	int SZ;
	void add(){
		seg.pb({-1, -1, INFLL, 0});
	}
	void Init(int x){
		SZ = x;
		add();
		init(0, 1, SZ);
	}
	void init(int idx, int s, int e){
		if(s==e){
			seg[idx].mn = dist[1][s];
			return;
		}
		seg[idx].l = seg.size(); add();
		seg[idx].r = seg.size(); add();
		init(seg[idx].l, s, (s+e)/2);
		init(seg[idx].r, (s+e)/2+1, e);
		seg[idx].mn = min(seg[seg[idx].l].mn, seg[seg[idx].r].mn);
	}
	void calc(int idx){
		if(seg[idx].lazy!=0 && seg[idx].l!=-1){
			seg[seg[idx].l].lazy+=seg[idx].lazy; 
			if(seg[seg[idx].l].mn!=INFLL)	seg[seg[idx].l].mn+=seg[idx].lazy;
			seg[seg[idx].r].lazy+=seg[idx].lazy; 
			if(seg[seg[idx].r].mn!=INFLL)	seg[seg[idx].r].mn+=seg[idx].lazy;
			seg[idx].lazy = 0;
		}
	}
	void Update(int x, int y, ll z){
		update(0, 1, SZ, x, y, z);
	}
	void update(int idx, int s, int e, int x, int y, ll z){
		calc(idx);
		if(x<=s && e<=y){
			if(seg[idx].mn==INFLL)	return;
			seg[idx].lazy+=z;
			seg[idx].mn+=z;
			return;
		}
		if(x>e || y<s)	return;
		update(seg[idx].l, s, (s+e)/2, x, y, z);
		update(seg[idx].r, (s+e)/2+1, e, x, y, z);
		seg[idx].mn = min(seg[seg[idx].l].mn, seg[seg[idx].r].mn);
	}
	ll Mn(int x, int y){
		return mn(0, 1, SZ, x, y);
	}
	ll mn(int idx, int s, int e, int x, int y){
		calc(idx);
		if(x<=s && e<=y)	return seg[idx].mn;
		if(x>e || y<s)	return INFLL;
		return min(mn(seg[idx].l, s, (s+e)/2, x, y), mn(seg[idx].r, (s+e)/2+1, e, x, y));
	}
}Seg;

void dfs(int x){
	in[x] = ++cnt;
	for(Edge i : gp[x]){
		if(i.x!=p[x]){
			dist[0][i.x] = dist[0][x] + (ll)i.l;
			p[i.x] = x;
			dfs(i.x);
		}
	}
	if(chk[x]){
		dist[1][in[x]] = dist[0][x];
	}else{
		dist[1][in[x]] = INFLL;
	}
	out[x] = cnt;
}

vector<pii> query1[MAX_N+1];
struct Query{
	int x, y, idx;
};
vector<Query> query2[MAX_N+1];
ll ans[MAX_N+1];

void dfs2(int x){
	if(x!=E){
		bool b = (Seg.Mn(in[x], out[x])==INFLL);
		for(pii i : query1[uidx[x]]){
			if(in[x]<=in[i.first] && in[i.first]<=out[x]){
				if(b){
					ans[i.second] = -2;
				}else{
					query2[i.first].pb({in[x], out[x], i.second});
				}
			}else{
				ans[i.second] = -1;
			}
		}
	}
	for(Query i : query2[x]){
		ans[i.idx] = Seg.Mn(i.x, i.y);
	}
	for(Edge i : gp[x]){
		if(i.x!=p[x]){
			uidx[i.x] = i.idx;
			Seg.Update(1, in[i.x]-1, (ll)i.l);
			Seg.Update(in[i.x], out[i.x], (ll)-i.l);
			Seg.Update(out[i.x]+1, N, (ll)i.l);
			dfs2(i.x);
			Seg.Update(1, in[i.x]-1, (ll)-i.l);
			Seg.Update(in[i.x], out[i.x], (ll)i.l);
			Seg.Update(out[i.x]+1, N, (ll)-i.l);
		}
	}
}

int main(){
	scanf("%d%d%d%d", &N, &S, &Q, &E);
	for(int i=1; i<N; i++){
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		gp[a].pb({b, c, i}); gp[b].pb({a, c, i});
	}	
	for(int i=1; i<=S; i++){
		int x; scanf("%d", &x); chk[x] = true;
	}
	dfs(E);
	Seg.Init(N);
	for(int i=1; i<=Q; i++){
		int x, y;
		scanf("%d%d", &x, &y);
		query1[x].pb({y, i});
	}
	dfs2(E);
	for(int i=1; i<=Q; i++){
		if(ans[i]==-1){
			printf("escaped\n");
		}else if(ans[i]==-2){
			printf("oo\n");
		}else{
			printf("%lld\n", ans[i]);
		}
	}
	return 0;
}

Compilation message (stderr)

valley.cpp: In function 'int main()':
valley.cpp:156:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d", &N, &S, &Q, &E);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:159:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &a, &b, &c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
valley.cpp:163:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x; scanf("%d", &x); chk[x] = true;
          ~~~~~^~~~~~~~~~
valley.cpp:169:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~

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