oj.uz

답안 #766150

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
766150 2023-06-25T10:44:36 Z Zflop Valley (BOI19_valley) C++14
100 / 100
 135 ms 54232 KB 
#include <bits/stdc++.h>
using namespace std;
 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

//#include "happiness.h"

/*
ID: 10002181
LANG: C++
TASK: lamps
*/
 
using str = string; // yay python!
using ld = long double; // or double, if TL is tight
using ll = long long;
using int64 = ll;
using db = double;
using ull = unsigned long long;
#define int ll
 
#define ch() getchar()
#define pc(x) putchar(x)
#define tcT template<class T
#define tcTU tcT, class U
tcT> using V = vector<T>;
tcT, size_t SZ> using AR = array<T,SZ>;
using vi = V<int>;
using vb = V<bool>;
using vpi = V<pair<int,int>>;
using vvi = V<vi>;
using vl = V<ll>;
using vd = V<ld>;
using vstr = V<str>;
 
#define all(x) begin(x), end(x)
#define sor(x) sort(all(x))
#define rev(x) reverse(all(x))
#define sz(x) (int)(x).size()
#define rall(x) x.rbegin(), x.rend()
#define AR array
 
// loops
#define F0R(i, a, b) for (int i=a; i<b;++i)
#define FOR(i, a) for (int i=0; i<a;++i)
#define FORn(i, a) for (int i=1; i<=a;++i)
#define ROF(i,a) for(int i=a-1; i >= 0;--i)
#define R0F(i,a,b) for(int i=a; i > b;--i)
#define ROFn(i,a) for(int i=a; i > 0;--i)
#define rep(a) FOR(_, a)
#define trav(i,x) for(auto& i:x)
 
// pairs
#define mp make_pair
#define pi pair <int, int>
#define f first
#define s second
 
// vectors
#define lb lower_bound
#define ub upper_bound
#define SUM(v) accumulate(all(v), 0LL)
#define MN(v) *min_element(all(v))
#define MX(v) *max_element(all(v))
#define UNIQUE(a) (a).erase(unique((a).begin(),(a).end()),(a).end())
#define eb emplace_back
#define ft front()
#define bk back()
#define ins insert
#define pf push_front
#define pb push_back
#define emt empty()
#define rsz resize
 
#define pob pop_back()
#define pof pop_front()
 
#define ts to_string
 
#define setIO()  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
 
ll MOD = 1e9+7;
const ll MAX = 100000000000;
const ll INF = 1e18; // not too close to LLONG_MAX
const ld PI = acos((ld)-1);
 
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
 
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1}; // for every grid problem!!
 
tcT> bool ckmin(T& a, const T& b) {
	return b < a ? a = b, 1 : 0; } // set a = min(a,b)
tcT> bool ckmax(T& a, const T& b) {
	return a < b ? a = b, 1 : 0; }
 
tcTU> T fstTrue(T lo, T hi, U f) {
	hi ++; assert(lo <= hi); // assuming f is increasing
	while (lo < hi) { // find first index such that f is true
		T mid = lo+(hi-lo)/2;
		f(mid) ? hi = mid : lo = mid+1;
	}
	return lo;
}
tcTU> T lstTrue(T lo, T hi, U f) {
	lo --; assert(lo <= hi); // assuming f is decreasing
	while (lo < hi) { // find first index such that f is true
		T mid = lo+(hi-lo+1)/2;
		f(mid) ? lo = mid : hi = mid-1;
	}
	return lo;
}
 
//INPUT
#define tcTUU tcT, class ...U
tcT> void re(complex<T>& c);
tcTU> void re(pair<T,U>& p);
tcT> void re(V<T>& v);
tcT, size_t SZ> void re(AR<T,SZ>& a);
 
tcT> void re(T& x) { cin >> x; }
void re(db& d) { str t; re(t); d = stod(t); }
void re(ld& d) { str t; re(t); d = stold(t); }
tcTUU> void re(T& t, U&... u) { re(t); re(u...); }
 
tcT> void re(complex<T>& c) { T a,b; re(a,b); c = {a,b}; }
tcTU> void re(pair<T,U>& p) { re(p.f,p.s); }
tcT> void re(V<T>& x) { trav(a,x) re(a); }
tcT> void rv(int n, V<T>& x) { x.rsz(n); re(x); }
 
//OUTPUT
namespace output {
	tcT> void PS(V<T>& x) { FOR(i,sz(x)) cout << x[i] << " \n"[i + 1 == sz(x)];}
	tcT> void W(pair<T,T>& x) { cout << x.f << ' ' << x.s << '\n'; }
	tcT> void PS(bool ok) { if(ok) cout << "YES\n"; else cout << "NO\n"; }
    template<class T1, class T2> void pr(const pair<T1,T2>& x);
    tcT, size_t SZ> void pr(const array<T,SZ>& x);
    tcT> void pr(const vector<T>& x);
    tcT> void pr(const set<T>& x);
    template<class T1, class T2> void pr(const map<T1,T2>& x);
 
    tcT> void pr(const T& x) { cout << x; }
    template<class Arg, class... Args> void pr(const Arg& first, const Args&... rest) {
        pr(first); pr(rest...);
    }
 
    template<class T1, class T2> void pr(const pair<T1,T2>& x) {
        pr("{",x.f,", ",x.s,"}");
    }
    tcT> void prContain(const T& x) {
        pr("{");
        bool fst = 1; trav(a,x) pr(!fst?", ":"",a), fst = 0;
        pr("}");
    }
    tcT, size_t SZ> void pr(const array<T,SZ>& x) { prContain(x); }
    tcT> void pr(const vector<T>& x) { prContain(x); }
    tcT> void pr(const set<T>& x) { prContain(x); }
    template<class T1, class T2> void pr(const map<T1,T2>& x) { prContain(x); }
 
    void ps() { pr("\n"); } // print w/ spaces
    template<class Arg> void ps(const Arg& first) { pr(first,"\n"); }
    template<class Arg, class... Args> void ps(const Arg& first, const Args&... rest) {
        pr(first," "); ps(rest...);
    }
}
 
using namespace output;
 
void setF(string fileName = "") {
	ios_base::sync_with_stdio(0); cin.tie(0);
	if((int)fileName.size()) {
		freopen((fileName+".in").c_str(), "r", stdin);
		freopen((fileName+".out").c_str(), "w", stdout);
	}
}
 
 
vb bb;
vi SIEVE(int N){ // sieve in O(N logN)
	vi pr;
	bb.rsz(N);
	bb[0] = bb[1] = true;
	vi g(N);
	F0R(i,2,N){
		if(!bb[i]){
			pr.pb(i);
			for (int j = i + i; j < N; j += i) bb[j] = true;
			}
		}
	return pr;
	}
 
 
 
template<class T> using ordset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
struct edge{
	int a;
	int b;
	int w;
	};
 
ll POW(ll x, ll y,ll mod){
    ll res = 1LL;
    x %= mod;
    while(y){
        if (y & 1LL)
            res *= x;
        res %= mod;
        x = (x*x) % mod;
        y >>= 1LL;
    }
    return res;
}
 
ll fact(ll x) { if(x) return x * fact(x - 1ll); return 1; }
 
vl fc;
void F(int N,ll MOD){
	fc.rsz(N + 1);
	fc[0] = 1;
	FORn(i,N) fc[i] = fc[i - 1] * i * 1ll % MOD;
	}
 
vl inv;
void I(int N,ll MOD){
	inv.rsz(N + 1);
	inv[N] = POW(fc[N],MOD - 2,MOD);
	for (int i = N; i ;--i) inv[i - 1] = inv[i] * 1ll * i % MOD;
	}
 
ll Cr(ll N,ll K,ll mod = MOD){
	if(K < 0) return 0;
	if(K > N) return 0;
	if(K == 0) return 1;
	return fc[N] * 1ll * inv[K] % mod * inv[N - K] % mod;
	}
ll Ar(ll N,ll K,ll mod){
	return fc[N] * inv[N - K] % mod;
	}
ll iv(int k,ll MOD){
  return POW(k,MOD-2,MOD);
}
ll gauss(ll x){
	return x * (x +  1) / 2;
	}
/*
 scanf("%lld", &testInteger);
 printf("%lld", testInteger);
 
 ____ ____ ____ ____ ____  ____
||f |||l |||o |||p |||p ||||y ||
||__|||__|||__|||__|||__||||__||
|/__\|/__\|/__\|/__\|/__\||/__\|
 
**/
const ll inf = (ll)1e14;
int N,S,Q,E,t;
vpi ad[100001];
int depth[100001],B[100001][3];
int tin[100001],tout[100001],par[100001];
ll pref[100001],d[100001],mn[20][100001],bj[20][100001];
bool shop[100001];
void dfs(int node,int parent){
	if(shop[node]) d[node] = pref[node];
	else d[node] = (ll)1e17;
	par[node] = parent;
	depth[node] = depth[parent] + 1;
	tin[node] = ++t;
	trav(x,ad[node])
		if(x.f != parent){
			pref[x.f] = pref[node] + x.s;
			dfs(x.f,node);
			ckmin(d[node],d[x.f]);
			}
	tout[node] = ++t;
	}
bool is_anc(int a,int b){
	return tin[a] <= tin[b] && tout[b] <= tout[a];
	}
ll jmp(int a,int k){
	int x = a;
	ll ans = d[a];
	for (int i = 0; i < 20;++i)
		if(k & (1 << i)){
			ans = min(ans,mn[i][a]);
			a = bj[i][a];
			}
	//ps(ans,pref[x]);
	return ans + pref[x];
	}
void solve(){
	cin >> N >> S >> Q >> E;
	FORn(i,N - 1){
		int a,b,w; cin >> a >> b >> w;
		ad[a].pb({b,w});
		ad[b].pb({a,w});
		B[i][0] = a;
		B[i][1] = b;
		B[i][2] = w;
		}
	FOR(i,S){
		int c; cin >> c;
		shop[c] = true;
		}
	dfs(E,0);
	
	for (int i = 1; i <= N;++i)
		d[i] -= 2 * pref[i];
	for (int i = 1; i <= N;++i){
		mn[0][i] = d[par[i]];
		bj[0][i] = par[i];
		}
	for (int i = 1; i < 20;++i)
		for (int j = 1; j <= N;++j){
			bj[i][j] = bj[i - 1][bj[i - 1][j]];
			mn[i][j] = min(mn[i - 1][j],mn[i - 1][bj[i - 1][j]]);
			}
	
	
	while(Q--){
		int road,village; cin >> road >> village;
		int n = B[road][0];
		int a = depth[B[road][0]];
		if(depth[B[road][0]] < depth[B[road][1]]){
			n = B[road][1];
			a = depth[B[road][1]];
			}
		int b = depth[village];
		if(b < a) ps("escaped");
		else if(!is_anc(n,village)) ps("escaped");	
		else {
			if(jmp(village,b - a) <= inf) cout << jmp(village,b - a) << '\n';
			else ps("oo");
			}
		}
	} 
// D(a) + D(b) - 2 * D(c)
main(){
	setIO();
	solve();
	}
 
// look out for out of bounds arrays
// And more importantly, is y a vowel? Damian:1
// <3 :L ._. <_<
// You have no idea how high I can fly
// code is my poetry
// don't forget to #include "happiness.h" to smile

Compilation message

valley.cpp:342:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  342 | main(){
      | ^~~~
valley.cpp: In function 'void setF(std::string)':
valley.cpp:175:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  175 |   freopen((fileName+".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:176:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  176 |   freopen((fileName+".out").c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 3088 KB Output is correct
2 Correct 3 ms 3052 KB Output is correct
3 Correct 3 ms 3028 KB Output is correct
4 Correct 4 ms 3028 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 3088 KB Output is correct
2 Correct 3 ms 3052 KB Output is correct
3 Correct 3 ms 3028 KB Output is correct
4 Correct 4 ms 3028 KB Output is correct
5 Correct 2 ms 3284 KB Output is correct
6 Correct 2 ms 3284 KB Output is correct
7 Correct 3 ms 3324 KB Output is correct
8 Correct 2 ms 3284 KB Output is correct
9 Correct 2 ms 3328 KB Output is correct
10 Correct 2 ms 3412 KB Output is correct
11 Correct 2 ms 3324 KB Output is correct
12 Correct 3 ms 3284 KB Output is correct
13 Correct 2 ms 3416 KB Output is correct
14 Correct 2 ms 3328 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 92 ms 47056 KB Output is correct
2 Correct 91 ms 47012 KB Output is correct
3 Correct 106 ms 47232 KB Output is correct
4 Correct 115 ms 48692 KB Output is correct
5 Correct 119 ms 48868 KB Output is correct
6 Correct 130 ms 50428 KB Output is correct

Subtask #4
41.0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 3088 KB Output is correct
2 Correct 3 ms 3052 KB Output is correct
3 Correct 3 ms 3028 KB Output is correct
4 Correct 4 ms 3028 KB Output is correct
5 Correct 2 ms 3284 KB Output is correct
6 Correct 2 ms 3284 KB Output is correct
7 Correct 3 ms 3324 KB Output is correct
8 Correct 2 ms 3284 KB Output is correct
9 Correct 2 ms 3328 KB Output is correct
10 Correct 2 ms 3412 KB Output is correct
11 Correct 2 ms 3324 KB Output is correct
12 Correct 3 ms 3284 KB Output is correct
13 Correct 2 ms 3416 KB Output is correct
14 Correct 2 ms 3328 KB Output is correct
15 Correct 92 ms 47056 KB Output is correct
16 Correct 91 ms 47012 KB Output is correct
17 Correct 106 ms 47232 KB Output is correct
18 Correct 115 ms 48692 KB Output is correct
19 Correct 119 ms 48868 KB Output is correct
20 Correct 130 ms 50428 KB Output is correct
21 Correct 85 ms 49500 KB Output is correct
22 Correct 87 ms 49368 KB Output is correct
23 Correct 92 ms 49504 KB Output is correct
24 Correct 109 ms 51264 KB Output is correct
25 Correct 135 ms 54232 KB Output is correct
26 Correct 90 ms 48864 KB Output is correct
27 Correct 111 ms 48632 KB Output is correct
28 Correct 97 ms 48844 KB Output is correct
29 Correct 116 ms 50092 KB Output is correct
30 Correct 126 ms 51396 KB Output is correct
31 Correct 86 ms 48788 KB Output is correct
32 Correct 90 ms 48672 KB Output is correct
33 Correct 127 ms 49020 KB Output is correct
34 Correct 112 ms 50548 KB Output is correct
35 Correct 118 ms 52880 KB Output is correct
36 Correct 103 ms 51348 KB Output is correct