Submission #902702

#	Time	Username	Problem	Language	Result	Execution time	Memory
902702		aqxa	Valley (BOI19_valley)	C++17	0 / 100	157 ms	76884 KiB

valley

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int N = 1e5 + 10; 
const ll inf = 1e18; 

int n, m, q, rt, s[N], gs[N] = { 0 }; 
vector<pair<int, int>> gr[N];
pair<int, int> edges[N]; 
set<int> nd[N]; 
map<int, ll> ans[N]; 

struct graph {
    vector<vector<int>> adj;
    int n;

    graph() {} 
    graph(int _n) : n(_n) {
        adj.resize(n);
    }

    inline void add(int x, int y) {
        adj[x].push_back(y); 
        adj[y].push_back(x); 
    }
};
struct lca_graph : graph {
    using graph::adj;
    using graph::n; 
    vector<vector<int>> par; 
    vector<int> lev, path; 
    int lv = 0, lg; 
    lca_graph(int _n) : graph(_n) {
        lg = __lg(n) + 1; 
        par = vector<vector<int>>(n, vector<int>(lg, -1)); 
        lev = vector<int>(n, 0); 
    }
    void make_lca(int x, int p) {
        path.push_back(x);
        lv++;
        lev[x] = lv;

        for (int i = 0; (1<<i) < path.size(); ++i) {
            par[x][i] = path[path.size()-1-(1<<i)];
        }

        for (auto u: adj[x]) {
            if (u != p) {
                make_lca(u, x);
            }
        }
        lv--;
        path.pop_back();
    }
    int ka(int u, int k) {
        if (k > lev[u] - 1) return 0; 
        while (k > 0) {
            int clg = (int) __lg(k);  
            k -= pow(2, lg);
            u = par[u][clg];
        }
        return u;
    }
    int lca(int u, int v) {
        int du = lev[u], dv = lev[v];
        if (du < dv) {
            v = ka(v, dv-du);
            dv = du;
        } else if (du > dv) {
            u = ka(u, du-dv);
            du = dv;
        }

        if (u == v) return u;

        for (int i = lg-1; i >= 0; --i) {
            if (par[u][i] != par[v][i]) {
                u = par[u][i];  
                v = par[v][i];
            }
        }

        return par[u][0];
    }
};
lca_graph g(1); 

ll dst[N]; 
void dfs_st(int x, int p) {
	dst[x] = inf; 
	if (gs[x]) dst[x] = 0; 
	for (auto [u, w]: gr[x]) {
		if (u == p) continue; 
		dfs_st(u, x); 
		dst[x] = min(dst[x], dst[u] + (ll) w); 
	}
}

ll tree[262144] = { inf }, lazy[262144] = { 0 }; 
void push(int L, int R, int id) {
	tree[id] += lazy[id]; 
	if (L != R) for (int i = 0; i < 2; ++i) lazy[2 * id + i] += lazy[id]; 
	lazy[id] = 0; 
}
void pull(int id) { tree[id] = min(tree[2 * id], tree[2 * id + 1]); }
void ch(int x, ll y, int L = 0, int R = 131072 - 1, int id = 1) {
	push(L, R, id); if (x < L || R < x) return;
	if (L == x && x == R) { tree[id] = y; return;  }
	int M = (L+R)/2; ch(x, y, L, M, 2 * id); 
	ch(x, y, M + 1, R, 2 * id + 1); pull(id);
}
void add(int l, int r, ll v, int L = 0, int R = 131072 - 1, int id = 1) {
	push(L, R, id); if (r < L || R < l) return;
	if (l <= L && R <= r) { lazy[id] = v; push(L, R, id); return; }
	int M = (L+R)/2; add(l, r, v, L, M, 2 * id); 
	add(l, r, v, M + 1, R, 2 * id + 1); pull(id);
}
ll get(int l, int r, int L = 0, int R = 131072 - 1, int id = 1) {
	push(L, R, id); if (r < L || R < l) return inf; 
	if (l <= L && R <= r) return tree[id]; 
	int M = (L+R)/2;
	return min(get(l, r, L, M, 2 * id), get(l, r, M + 1, R, 2 * id + 1));
}


int csz = 0; 
void dfs_ans(int x, int p) {
	ch(csz, dst[x]); 

	for (auto u: nd[x]) {
		int ld = g.lev[x] - g.lev[u]; 
		ans[x][u] = get(csz - ld, csz); 
	}
	csz++; 

	for (auto [u, w]: gr[x]) {
		if (u == p) continue; 
		add(0, csz, (ll)w); 
		dfs_ans(u, x); 
		add(0, csz, (ll)-w); 
	}

	csz--; 
	ch(csz, inf); 
}

int main() {
	cin >> n >> m >> q >> rt; 
	g = lca_graph(n);  
	for (int i = 0; i < n - 1; ++i) {
		int x, y, w; 
		cin >> x >> y >> w; 
		edges[i] = make_pair(--x, --y); 
		g.add(x, y); 
		gr[x].push_back({y, w}); 
		gr[y].push_back({x, w}); 
	}
	for (int i = 0; i < m; ++i) {
		cin >> s[i]; 
		gs[--s[i]] = 1; 
	}
	g.make_lca(--rt, -1); 

	int qi[q], qs[q]; 
	for (int i = 0; i < q; ++i) {
		cin >> qi[i] >> qs[i]; 
		qi[i]--; qs[i]--; 
		
		int x = edges[qi[i]].first, y = edges[qi[i]].second; 
		int z = g.lca(x, y) ^ x ^ y; 
		if (g.lca(z, qs[i]) == z) {
			nd[qs[i]].insert(z); 
		} 
	}
	
	dfs_st(rt, -1); 
	dfs_ans(rt, -1); 
	for (int i = 0; i < q; ++i) {
		int x = edges[qi[i]].first, y = edges[qi[i]].second; 
		int z = g.lca(x, y) ^ x ^ y; 
		if (g.lca(z, qs[i]) == z) {
			ll cans = ans[qs[i]][z]; 
			if (cans == inf) cout << "oo\n";
			else cout << cans << "\n";
		} else {
			cout << "escaped\n";
		}
	}

	return 0;
}

Compilation message (stderr)

valley.cpp: In member function 'void lca_graph::make_lca(int, int)':
valley.cpp:45:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         for (int i = 0; (1<<i) < path.size(); ++i) {
      |                         ~~~~~~~^~~~~~~~~~~~~

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