| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1096315 |
2024-10-04T09:26:17 Z |
tuandq |
Valley (BOI19_valley) |
C++17 |
|
100 ms |
34156 KB |
#include <bits/stdc++.h>
using namespace std ;
typedef long long ll ;
typedef long double ld ;
typedef pair<int, int> pii ;
typedef pair<int, long long> pil ;
typedef pair<long long, int> pli ;
typedef pair<long long, long long> pll ;
typedef vector<int> vi ;
typedef vector<long long> vll ;
#define bitc(n) (__builtin_popcountll(n))
#define clz(n) (__builtin_clzll(n))
#define ctz(n) (__builtin_ctzll(n))
#define lg(n) (31 - __builtin_clz(n))
#define MASK(k) (1ll << (k))
#define getbit(n, k) ((n) >> (k) & 1)
#define flipbit(n, k) ((n) ^ (1ll << (k)))
#define ton(n, k) ((n) | (1ll << (k)))
#define toff(n, k) ((n) & ~(1ll << (k)))
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back
#define lwb lower_bound
#define upb upper_bound
#define sz(x) (int)(x.size())
#define all(x) x.begin(),x.end()
#define taskname "input"
template<class X, class Y> bool maximize(X &x, const Y &y) {return (x < y ? x = y, true : false) ;}
template<class X, class Y> bool minimize(X &x, const Y &y) {return (x > y ? x = y, true : false) ;}
template<class X>
void remove_dup(vector<X> &ve) {
sort(ve.begin(), ve.end()) ;
ve.resize(unique(ve.begin(), ve.end()) - ve.begin()) ;
}
const ll mod = 1e9 + 7 ;
const ll INF = 1e18 ;
const int inf = 1e9 ;
const int N = 1e5 + 5 ;
/* Some Peach Tea Is Great ;-; */
/* Author : Tuandq */
struct E {
int u, v, w ;
E() {}
E(int _u, int _v, int _w): u(_u), v(_v), w(_w) {}
};
int a[N], n, m, q, hel ;
vector<int> adj[N] ;
pii query[N] ;
E e[N] ;
namespace sub4 {
#define tiii tuple<int, int, int>
const int LG = 17 ;
int up[LG][N], h[N], st[N], en[N], in[N], dfscnt = 0 ;
pll dp[N << 1], g[N] ;
vector<tiii> ke[N] ;
bool mark[N] ;
ll dis[N] ;
void dfs(int u, int par) {
st[u] = ++dfscnt ;
for(int i : adj[u]) {
int v = e[i].u ^ e[i].v ^ u ;
if(v != par) {
dis[v] = dis[u] + e[i].w ;
h[v] = h[u] + 1 ;
up[0][v] = u ;
in[v] = i ;
dfs(v, u) ;
}
}
en[u] = dfscnt ;
}
bool inside(int u, int v) {
return st[u] <= st[v] && en[v] <= en[u] ;
}
int get_lca(int u, int v) {
if(inside(u, v)) return u ;
for(int k = lg(u) - 1; k > -1; k --) {
int nxt = up[k][u] ;
if(!inside(nxt, v)) {
u = nxt ;
}
}
return up[0][u] ;
}
void modify(pll &cur, ll x) {
if(x <= cur.fi) {
cur.se = cur.fi ;
cur.fi = x ;
}
else minimize(cur.se, x) ;
}
pll get_dp(int u, int par, int idx) {
if(idx != -1 && dp[idx].fi != -1ll) {
return dp[idx] ;
}
pll res(mark[u] ? 0ll : INF, INF) ;
for(tiii cur : ke[u]) {
int v = get<0>(cur) ;
int w = get<1>(cur) ;
int nxt = get<2>(cur) ;
if(v != par) {
modify(res, get_dp(v, u, nxt).fi + w) ;
}
}
if(idx != -1) {
dp[idx] = res ;
}
return res ;
}
ll get_dis(int u, int v) {
return dis[u] + dis[v] - 2ll * dis[get_lca(u, v)] ;
}
int get_idx(int i, int u, int v) {
return i * 2 - (e[i].u == u) ;
}
void print(ll x) {
if(x >= INF) {
cout << "oo\n" ; return ;
}
cout << x << '\n' ;
}
void trySolve(int del, int town) {
int u = e[del].u ;
int v = e[del].v ;
if(h[u] > h[v]) swap(u, v) ;
if(!inside(v, town)) {
cout << "escaped\n" ; return ;
}
int idx1 = get_idx(del, u, v) ;
ll len = get_dis(town, v) + get_dp(v, -1, idx1).fi ;
if(g[town].fi != len && len < INF) {
print(g[town].fi) ;
return ;
}
int p = up[0][u] ;
int idx2 = p ? get_idx(in[u], p, u) : -1 ;
pll x = get_dp(u, -1, idx2) ;
ll y = get_dp(v, -1, idx1).fi + e[in[v]].w ;
// cerr << g[town].se << ' ' << x.fi << ' ' << x.se << ' ' << y << endl ;
ll z = get_dis(u, u) + (x.fi != y && y < INF ? x.fi : x.se) ;
print(min(g[town].se, z)) ;
}
void solve() {
for(int i = 1; i <= m; i ++) {
mark[a[i]] = true ;
}
for(int i = 1; i < n; i ++) {
ke[e[i].u].emplace_back(e[i].v, e[i].w, i * 2 - 1) ;
ke[e[i].v].emplace_back(e[i].u, e[i].w, i * 2) ;
dp[i * 2 - 1] = dp[i * 2] = mp(-1ll, -1ll) ;
}
for(int i = 1; i <= n; i ++) {
g[i] = get_dp(i, 0, -1) ;
}
dfs(hel, 0) ;
for(int j = 1; (1 << j) <= n; j ++) {
for(int i = 1; i <= n; i ++) {
up[j][i] = up[j - 1][up[j - 1][i]] ;
}
}
for(int i = 1; i <= q; i ++) {
trySolve(query[i].fi, query[i].se) ;
}
}
}
signed main() {
ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0) ;
if(fopen(taskname".inp", "r")) {
freopen(taskname".inp", "r", stdin) ;
freopen(taskname".out", "w", stdout) ;
}
cin >> n >> m >> q >> hel ;
for(int i = 1; i < n; i ++) {
int u, v, w ; cin >> u >> v >> w ;
adj[u].push_back(i) ;
adj[v].push_back(i) ;
e[i] = E(u, v, w) ;
}
for(int i = 1; i <= m; i ++) {
cin >> a[i] ;
}
for(int i = 1; i <= q; i ++) {
cin >> query[i].fi >> query[i].se ;
}
return sub4::solve(), 0 ;
}
Compilation message
valley.cpp: In function 'int main()':
valley.cpp:198:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
198 | freopen(taskname".inp", "r", stdin) ;
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:199:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
199 | freopen(taskname".out", "w", stdout) ;
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
16732 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
16732 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
86 ms |
29772 KB |
Output is correct |
| 2 |
Correct |
90 ms |
29164 KB |
Output is correct |
| 3 |
Correct |
87 ms |
29008 KB |
Output is correct |
| 4 |
Correct |
99 ms |
30804 KB |
Output is correct |
| 5 |
Correct |
87 ms |
30888 KB |
Output is correct |
| 6 |
Correct |
100 ms |
34156 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
16732 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
