| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 655149 |
2022-11-03T10:40:53 Z |
HuyKoCoNy |
Valley (BOI19_valley) |
C++17 |
|
4 ms |
5076 KB |
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include<bits/stdc++.h>
using namespace std;
// __builtin_popcount
// __builtin_ctz
#define int long long
#define pii pair<int, int>
#define duoble long double
#define endl '\n'
#define fi first
#define se second
#define mapa make_pair
#define pushb push_back
#define pushf push_front
#define popb pop_back
#define popf pop_front
#define o_ ordered_
#define ins insert
#define era erase
#define pqueue priority_queue
#define minele min_element
#define maxele max_element
#define lb lower_bound // >=
#define ub upper_bound // >
#define debug cout << "NO ERROR", exit(0)
#define FAST ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define ALL(v) v.begin(), v.end()
#define SZ(v) (int)v.size()
#define sqr(x) ((x) * (x))
template<class X, class Y>
bool minimize(X &x, const Y &y) {
if (x > y) {
x = y;
return true;
}
return false;
}
template<class X, class Y>
bool maximize(X &x, const Y &y) {
if (x < y) {
x = y;
return true;
}
return false;
}
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int Rand(const int &l, const int &r) {
assert(l <= r);
int sz = (r - l + 1);
return l + rd() % sz;
}
const int MOD = 1e9 + 7; //998244353;
const int LOG = 18;
const int INF = 1e18 + 7;
const int d4x[4] = {-1, 1, 0, 0};
const int d4y[4] = {0, 0, 1, -1};
const char c4[4] = {'U', 'D', 'R', 'L'};
const int d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};
// #define LENGTH 1000005
// #define NMOD 2
// #define BASE 256
// const int HashMod[] = {(int)1e9 + 7, (int)1e9 + 2277, (int)1e9 + 5277, (int)1e9 + 8277, (int)1e9 + 9277};
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// #define o_set tree<int, null_type,less<int>, rb_tree_tag, tree_order_statistics_node_update>
// *(s.find_by_order(2)) : 3rd element in the set i.e. 6
// s.order_of_key(25) : Count of elements strictly smaller than 25 is 4
/* Listen music of IU before enjoy my code */
const int LimN = 1e5 + 5;
int NumNode, SpecNode, NumShop, q, timeDFS;
int high[LimN], par[LimN][LOG], LOG2[LimN], w[LimN], f[LimN], num[LimN];
int mnf[LimN][LOG], mng[LimN][LOG], mn[LimN], pref[LimN], suf[LimN];
bool shop[LimN];
pii edge[LimN];
vector<pii> adj[LimN], nadj[LimN];
void make_tree() {
function<void(int, int)> dfs = [&](int u, int p) {
num[u] = ++timeDFS;
for (auto [v, c] : adj[u]) if (v != p) {
nadj[u].pushb(pii(v, c));
dfs(v, u);
}
};
dfs(1, 0);
for (int i = 1; i <= NumNode; i++) {
swap(adj[i], nadj[i]);
// cout << i << endl;
// for (auto [v, c] : adj[i]) cout << v << " " << c << endl;
// cout << endl;
}
}
void dfs(int u) {
for (auto [v, c] : adj[u]) {
high[v] = high[u] + 1;
w[v] = w[u] + c;
par[v][0] = u;
dfs(v);
}
pref[0] = suf[SZ(adj[u]) + 1] = mn[u];
for (int i = 1; i <= SZ(adj[u]); i++) {
auto [v, c] = adj[u][i - 1];
pref[i] = suf[i] = mn[v] + c;
minimize(pref[i], pref[i - 1]);
}
for (int i = SZ(adj[u]); i >= 1; i--) {
minimize(suf[i], suf[i + 1]);
auto [v, c] = adj[u][i - 1];
f[v] = min(pref[i - 1], suf[i + 1]);
mnf[v][0] = f[v] - w[u];
mng[v][0] = f[v] + w[u];
}
mn[u] = suf[1];
}
bool IsChild(int u, int p) {
return num[u] >= num[p];
}
int getmnf(int u, int k) {
int ans = INF;
// cout << "uk" << u << " " << k << endl;
for (int i = LOG2[k]; i >= 0; i--) if (k >= MASK(i)) {
minimize(ans, mnf[u][i]);
k -= MASK(i);
u = par[u][i];
}
return ans;
}
int getmng(int u, int k) {
int ans = INF;
for (int i = LOG2[k]; i >= 0; i--) if (k >= MASK(i)) {
minimize(ans, mng[u][i]);
k -= MASK(i);
u = par[u][i];
}
return ans;
}
int jump(int u, int k) {
for (int i = LOG2[k]; i >= 0; i--) if (k >= MASK(i)) {
k -= MASK(i);
u = par[u][i];
}
return u;
}
bool ok(int sta, int p, int child) {
int oksta = IsChild(sta, child);
int okspecnode = IsChild(SpecNode, child);
return !(oksta ^ okspecnode);
}
void RMQ() {
make_tree();
high[1] = 1;
dfs(1);
for (int i = 2; i <= NumNode; i++) LOG2[i] = LOG2[i / 2] + 1;
for (int j = 1; j < LOG; j++) {
for (int i = 1; i <= NumNode; i++) {
par[i][j] = par[par[i][j - 1]][j - 1];
mnf[i][j] = min(mnf[i][j - 1], mnf[par[i][j - 1]][j - 1]);
mng[i][j] = min(mng[i][j - 1], mng[par[i][j - 1]][j - 1]);
}
}
}
int lca(int u, int v) {
if (high[u] < high[v]) swap(u, v);
for (int i = LOG2[high[u] - high[v]]; i >= 0; i--) {
if (high[par[u][i]] >= high[v]) {
u = par[u][i];
}
}
if (u == v) return u;
for (int i = LOG2[high[u]]; i >= 0; i--) {
if (par[u][i] != par[v][i]) {
u = par[u][i];
v = par[v][i];
}
}
return par[u][0];
}
void solve() {
cin >> NumNode >> NumShop >> q >> SpecNode;
for (int i = 1; i < NumNode; i++) {
int u, v, c;
cin >> u >> v >> c;
edge[i] = pii(u, v);
adj[u].pushb(pii(v, c));
adj[v].pushb(pii(u, c));
}
fill(mn + 1, mn + 1 + NumNode, INF);
// for (int i = 1; i <= NumNode; i++) cout << mn[i] << " ";
// cout << endl;
for (int i = 1; i <= NumShop; i++) {
int x;
cin >> x;
shop[x] = true;
mn[x] = 0;
// cout << "shop" << x << endl;
}
RMQ();
for (int i = 1; i < NumNode; i++) {
auto [u, v] = edge[i];
if (high[u] > high[v]) swap(edge[i].fi, edge[i].se);
}
// for (int i = 1; i <= NumNode; i++) {
// cout << i << " " << mn[i] << " " << f[i] << " " << w[i] << endl;
// }
for (int i = 1; i <= q; i++) {
int id, sta;
cin >> id >> sta;
auto [p, child] = edge[id];
if (ok(sta, p, child)) {
cout << "escaped" << endl;
}
else {
int ans = INF, resa, resb;
// cout << p << " " << child << endl;
if (IsChild(p, sta)) {
// cout << "type1" << endl;
// cout << f[child] << endl;
resa = getmng(child, high[child] - high[sta]) - w[sta];
resb = getmnf(sta, high[sta] - high[1]) + w[sta];
ans = min(resa, resb);
}
else if (IsChild(sta, child)) {
// cout << "type2" << endl;
resa = getmnf(sta, high[sta] - high[child]) + w[sta];
resb = mn[sta];
// cout << f[sta] << " " << sta << " " << child << " " << resa << endl;
ans = min(resa, resb);
// debug;
}
else {
// cout << "type3" << endl;
int root = lca(sta, p);
resa = getmnf(sta, high[sta] - high[root]) + w[sta];
resb = getmng(child, high[child] - high[root]) - w[root] + w[sta];
ans = min({resa, resb, mn[sta]});
}
minimize(ans, INF);
if (ans == INF) cout << "oo" << endl;
else cout << ans << endl;
}
}
}
/* Authors: Nguyen Minh Huy from Le Quy Don high school for Gifted Students Da Nang */
signed main() {
#ifndef ONLINE_JUDGE
freopen("ab.inp", "r", stdin);
freopen("ab.out", "w", stdout);
#else
// freopen("task.inp", "r", stdin);
// freopen("task.out", "w", stdout);
#endif
FAST;
bool TestCase = 0;
int NumTest = 1;
//cin >> NumTest;
for (int i = 1; i <= NumTest; i++) {
if (TestCase) cout << "Case" << " " << i << ": ";
solve();
}
}
Compilation message
valley.cpp: In function 'int main()':
valley.cpp:301:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
301 | freopen("ab.inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
valley.cpp:302:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
302 | freopen("ab.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
