Submission #891741

#	Time	Username	Problem	Language	Result	Execution time	Memory
891741		CutSandstone	Valley (BOI19_valley)	C++17	100 / 100	268 ms	41296 KiB

valley

#include <bits/stdc++.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt,tune=native")
#define vi vector<int>
#define vb vector<bool>
#define vl vector<long long>
#define vii vector<vector<int>>
#define vll vector<vector<long long>>
#define pi pair<int, int>
#define pl pair<ll, ll>
#define vpi vector<pair<int, int>>
#define vpl vector<pair<ll, ll>>
#define a first
#define b second
#define str string
#define pb push_back
#define hset unordered_set
#define hmap unordered_map
const int mod = 1e9+7;
const int m = 998244353;
//16094558932
using namespace std;
using ll = long long;
using ull = unsigned ll;
template<size_t SZ> struct RMQ {
	static constexpr int level(int x) { return 31-__builtin_clz(x); }
	array<array<int,SZ>, level(SZ)+1> jmp;
	vi v;
	void init(const vi& depth, const vi& ind){
		v = depth;
		assert(ind.size() <= SZ);
		copy(begin(ind), end(ind), begin(jmp[0]));
		for (int j = 1; 1<<j <= ind.size(); ++j)
			for(int i = 0; i<ind.size()-(1<<j)+1; i++){
				int a = jmp[j-1][i], b = jmp[j-1][i+(1<<(j-1))];
				jmp[j][i] = depth[a] < depth[b] ? a:b;
			}
	}
	int query(int l, int r) {
		if(l > r) swap(l, r);
		int d = level(r-l+1);
		int a = jmp[d][l], b = jmp[d][r-(1<<d)+1];
		return v[a] < v[b] ? a:b;
	}
};
struct BIT {
	int N; vl data;
	void init(int sz){N = sz+1; data.resize(sz+1, 0); }
	void add(int p, ll x) { for (p++;p<=N;p+=p&-p) data[p-1] = (data[p-1]+x)%m; }
	ll sum(int l, int r) { return (sum(r)-(l==0?0:sum(l-1))+m)%m; }
	ll sum(int r) { ll s = 0; r++; for(;r;r-=r&-r)s = (s+data[r-1])%m; return s; }
	int lower_bound(ll sum) {
		if (sum <= 0) return -1;
		int pos = 0;
		for (int pw = 1<<25; pw; pw >>= 1) {
			int npos = pos+pw;
			if (npos <= N && data[npos-1] < sum)
				pos = npos, sum -= data[pos-1];
		}
		return pos;
	}
};
struct DSU {
	vector<int> e;
	DSU(int N) { e = vector<int>(N, -1); }
 
	// get representive component (uses path compression)
	int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
 
	bool same_set(int a, int b) { return get(a) == get(b); }
 
	int size(int x) { return -e[get(x)]; }
 
	bool unite(int x, int y) {  // union by size
		x = get(x), y = get(y);
		if (x == y) return false;
		if (e[x] > e[y]) swap(x, y);
		e[x] += e[y];
		e[y] = x;
		return true;
	}
};
struct Hasher {
	vl h1, h2, p1, p2, v1, v2;
	const ll m1 = 1283, m2 = 2793;
	const ll i1 = 439594703, i2 = 7876835;
	Hasher(string s){
		int n = s.size();
		h1.resize(n);
		h2.resize(n);
		p1.resize(n);
		p2.resize(n);
		v1.resize(n);
		v2.resize(n);
		for(int i = 0; i<n; i++){
			p1[i] = (i?p1[i-1]:i1)*m1%mod;
			p2[i] = (i?p2[i-1]:i2)*m2%mod;
			v1[i] = (i?v1[i-1]:m1)*i1%mod;
			v2[i] = (i?v2[i-1]:m2)*i2%mod;
			h1[i] = ((i?h1[i-1]:0)+p1[i]*(s[i]-'a'+1)%mod)%mod;
			h2[i] = ((i?h2[i-1]:0)+p2[i]*(s[i]-'a'+1)%mod)%mod;
		}
	}
	pi get(int l, int r){
		ll a = (h1[r]-(l?h1[l-1]:0)+mod)%mod;
		ll b = (h2[r]-(l?h2[l-1]:0)+mod)%mod;
		return {(int)(a*v1[l]%mod), (int)(b*v2[l]%mod)};
	}
};
struct SegTree {
	vll mem;
	int n;
	public:
	SegTree(int N){
		n = N;
		mem.resize(n<<1, vl(4));
	}
	void set(int ind, ll val){
		for(mem[ind+=n] = {val,val,val,val}; ind>>=1;) mem[ind] = comb(mem[ind<<1], mem[ind<<1|1]);
	}
	ll get(int l, int r){
		vl L = {}, R = {};
		for(l+=n,r+=n+1;l<r;l>>=1,r>>=1){
			if(l&1) L = comb(L, mem[l++]);
			if(r&1) R = comb(mem[--r], R);
		}
		return comb(L, R)[0];
	}
	private:
	vl comb(vl& l, vl& r){
		if(l.size() == 0) return r;
		if(r.size() == 0) return l;
		return {max({l[0], r[0], l[2]+r[1]}),
				max({l[3]+r[1], l[1]}),
				max({r[3]+l[2], r[2]}),
				l[3]+r[3]
			};
	}
};
class LZST {
private:
    class Node {
    public:
        ll l, r;
        Node *left, *right;
        ll val = 0, max = 0, min = 0, add = 0;
        bool isSet = false;
        Node(ll a, ll b) : l(a), r(b), left(nullptr), right(nullptr) {}
        void set(ll num) {
            isSet = true;
            add = max = min = num;
            val = num * (r - l + 1);
        }
        void addF(ll num) {
            add += num;
            val += num * (r - l + 1);
            max += num;
            min += num;
        }
        void prop() {
            ll mid = (l + r) >> 1;
            if (left == nullptr) left = new Node(l, mid);
            if (right == nullptr) right = new Node(mid + 1, r);
            if (isSet) {
                isSet = false;
                if (l != r) {
                    left->set(add);
                    right->set(add);
                }
            } else if (add != 0) {
                if (l != r) {
                    left->addF(add);
                    right->addF(add);
                }
            }
            add = 0;
        }
        void upd() {
            val = left->val + right->val;
            min = std::min(left->min, right->min);
            max = std::max(left->max, right->max);
        }
    };
    Node* top;
    void set(ll s, ll e, ll num, Node* curr) {
        if (curr->l == s && curr->r == e) {
            curr->set(num);
            return;
        }
        curr->prop();
        if (e <= curr->left->r) set(s, e, num, curr->left);
        else if (s >= curr->right->l) set(s, e, num, curr->right);
        else {
            set(s, curr->left->r, num, curr->left);
            set(curr->right->l, e, num, curr->right);
        }
        curr->upd();
    }
    void add(ll s, ll e, ll num, Node* curr) {
        if (curr->l == s && curr->r == e) {
            curr->addF(num);
            return;
        }
        curr->prop();
        if (e <= curr->left->r) add(s, e, num, curr->left);
        else if (s >= curr->right->l) add(s, e, num, curr->right);
        else {
            add(s, curr->left->r, num, curr->left);
            add(curr->right->l, e, num, curr->right);
        }
        curr->upd();
    }
    ll sum(ll s, ll e, Node* curr) {
        if (curr->l == s && curr->r == e) return curr->val;
        curr->prop();
        if (e <= curr->left->r) return sum(s, e, curr->left);
        if (s >= curr->right->l) return sum(s, e, curr->right);
        return sum(s, curr->left->r, curr->left) + sum(curr->right->l, e, curr->right);
    }
    ll max(ll s, ll e, Node* curr) {
        if (curr->l == s && curr->r == e) return curr->max;
        curr->prop();
        if (e <= curr->left->r) return max(s, e, curr->left);
        if (s >= curr->right->l) return max(s, e, curr->right);
        return std::max(max(s, curr->left->r, curr->left), max(curr->right->l, e, curr->right));
    }
    ll min(ll s, ll e, Node* curr) {
        if (curr->l == s && curr->r == e) return curr->min;
        curr->prop();
        if (e <= curr->left->r) return min(s, e, curr->left);
        if (s >= curr->right->l) return min(s, e, curr->right);
        return std::min(min(s, curr->left->r, curr->left), min(curr->right->l, e, curr->right));
    }
public:
    LZST(ll N) {
        assert(N > 0);
        top = new Node(0, N - 1);
    }
    ll get(ll s) {
        assert(s >= top->l && s <= top->r);
        Node* curr = top;
        stack<Node*> stk;
        while (curr->l != curr->r) {
            stk.push(curr);
            curr->prop();
            if (s <= curr->left->r) curr = curr->left;
            else curr = curr->right;
        }
        while (!stk.empty()) stk.top()->upd(), stk.pop();
        return curr->val;
    }
    ll sum(ll s, ll e) {
        assert(s >= top->l && s <= top->r && e >= top->l && e <= top->r && s <= e);
        return sum(s, e, top);
    }
    ll max(ll s, ll e) {
        assert(s >= top->l && s <= top->r && e >= top->l && e <= top->r && s <= e);
        return max(s, e, top);
    }
    ll min(ll s, ll e) {
        assert(s >= top->l && s <= top->r && e >= top->l && e <= top->r && s <= e);
        return min(s, e, top);
    }
    void add(ll s, ll e, ll num) {
        assert(s >= top->l && s <= top->r && e >= top->l && e <= top->r && s <= e);
        add(s, e, num, top);
    }
    void add(ll s, ll num) {
        assert(s >= top->l && s <= top->r);
        add(s, s, num, top);
	}
    void set(ll s, ll e, ll num) {
        assert(s >= top->l && s <= top->r && e >= top->l && e <= top->r && s <= e);
        set(s, e, num, top);
    }
    void set(ll s, ll num) {
        assert(s >= top->l && s <= top->r);
        set(s, s, num, top);
    }
};
const string name = "";
const int MAXN = 1e5;
vpi g[MAXN], q[MAXN];
int st[MAXN], en[MAXN], timer = 0, n;
ll depth[MAXN], ans[MAXN];
void dfs1(int s, int p, ll d){
	st[s] = timer++;
	depth[s] = d;
	for(pi& a: g[s]) if(a.a != p)
		dfs1(a.a, s, d+a.b);
	en[s] = timer-1;
}
void dfs2(int s, int p, LZST& dis){
	for(pi& a: q[s]){
		if(st[s] < st[a.a] || st[s] > en[a.a]) ans[a.b] = -1;
		else{
			ll curr = dis.min(st[a.a], en[a.a]);
			if(curr > 1e15) ans[a.b] = -2;
			else ans[a.b] = curr;
		}
	}
	for(pi& a: g[s]) if(a.a != p){
		dis.add(0, n-1, a.b);
		dis.add(st[a.a], en[a.a], -(a.b<<1));
		dfs2(a.a, s, dis);
		dis.add(st[a.a], en[a.a], a.b<<1);
		dis.add(0, n-1, -a.b);
	}
}
int main() {
	ios::sync_with_stdio(false);
  	cin.tie(nullptr);
	int s, Q, e; cin >> n >> s >> Q >> e;
	for(int i = 0; i<n; i++){
		g[i].clear();
		q[i].clear();
		timer = 0;
	}
	vpi roads(n-1);
	for(int i = 0; i<n-1; i++){
		int a, b, w; cin >> a >> b >> w;
		g[--a].pb({--b, w});
		g[b].pb({a, w});
		roads[i] = {a, b};
	}
	dfs1(--e, -1, 0);
	LZST dis(n);
	for(int i = 0; i<n; i++) dis.add(i, i, LLONG_MAX>>3);
	while(s--){
		int c; cin >> c; --c;
		dis.add(st[c], st[c], depth[c]-(LLONG_MAX>>3));
	}
	for(int i = 0; i<Q; i++){
		int I, r; cin >> I >> r; --I;
		q[r-1].pb({depth[roads[I].a] > depth[roads[I].b] ? roads[I].a:roads[I].b, i});
	}
	dfs2(e, -1, dis);
	for(int i = 0; i<Q; i++) cout << (ans[i]==-1?"escaped":ans[i]==-2?"oo":to_string(ans[i])) << "\n";
}

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