oj.uz

답안 #171033

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
171033 2019-12-27T06:20:51 Z dndhk Valley (BOI19_valley) C++14
100 / 100
 609 ms 39896 KB 
#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

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.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 7928 KB Output is correct
2 Correct 11 ms 7800 KB Output is correct
3 Correct 12 ms 7804 KB Output is correct
4 Correct 12 ms 7800 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 7928 KB Output is correct
2 Correct 11 ms 7800 KB Output is correct
3 Correct 12 ms 7804 KB Output is correct
4 Correct 12 ms 7800 KB Output is correct
5 Correct 10 ms 7544 KB Output is correct
6 Correct 10 ms 7544 KB Output is correct
7 Correct 11 ms 7608 KB Output is correct
8 Correct 11 ms 7584 KB Output is correct
9 Correct 10 ms 7544 KB Output is correct
10 Correct 11 ms 7684 KB Output is correct
11 Correct 11 ms 7672 KB Output is correct
12 Correct 12 ms 7672 KB Output is correct
13 Correct 11 ms 7672 KB Output is correct
14 Correct 11 ms 7676 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 496 ms 28504 KB Output is correct
2 Correct 523 ms 28120 KB Output is correct
3 Correct 541 ms 27992 KB Output is correct
4 Correct 579 ms 33496 KB Output is correct
5 Correct 520 ms 31832 KB Output is correct
6 Correct 609 ms 38612 KB Output is correct

Subtask #4
41.0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 7928 KB Output is correct
2 Correct 11 ms 7800 KB Output is correct
3 Correct 12 ms 7804 KB Output is correct
4 Correct 12 ms 7800 KB Output is correct
5 Correct 10 ms 7544 KB Output is correct
6 Correct 10 ms 7544 KB Output is correct
7 Correct 11 ms 7608 KB Output is correct
8 Correct 11 ms 7584 KB Output is correct
9 Correct 10 ms 7544 KB Output is correct
10 Correct 11 ms 7684 KB Output is correct
11 Correct 11 ms 7672 KB Output is correct
12 Correct 12 ms 7672 KB Output is correct
13 Correct 11 ms 7672 KB Output is correct
14 Correct 11 ms 7676 KB Output is correct
15 Correct 496 ms 28504 KB Output is correct
16 Correct 523 ms 28120 KB Output is correct
17 Correct 541 ms 27992 KB Output is correct
18 Correct 579 ms 33496 KB Output is correct
19 Correct 520 ms 31832 KB Output is correct
20 Correct 609 ms 38612 KB Output is correct
21 Correct 396 ms 26704 KB Output is correct
22 Correct 404 ms 26304 KB Output is correct
23 Correct 425 ms 26104 KB Output is correct
24 Correct 443 ms 32360 KB Output is correct
25 Correct 459 ms 39896 KB Output is correct
26 Correct 421 ms 26748 KB Output is correct
27 Correct 432 ms 26328 KB Output is correct
28 Correct 442 ms 26276 KB Output is correct
29 Correct 502 ms 30680 KB Output is correct
30 Correct 509 ms 34092 KB Output is correct
31 Correct 468 ms 27096 KB Output is correct
32 Correct 477 ms 26800 KB Output is correct
33 Correct 505 ms 26968 KB Output is correct
34 Correct 561 ms 32592 KB Output is correct
35 Correct 594 ms 39664 KB Output is correct
36 Correct 517 ms 32984 KB Output is correct