| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1096426 |
2024-10-04T12:29:45 Z |
snowmel |
Valley (BOI19_valley) |
C++17 |
|
89 ms |
16372 KB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int N, S, Q, H, C;
vector<pair<int,int>> QRS;
vector<tuple<int,int,ll>> edges;
vector<int> villages;
namespace sub12 {
vector<vector<int>> adj;
vector<int> is_village;
bool check() {
return 1ll * N * Q <= int(1e6);
}
array<ll,3> dfs(int u, int p = -1) {
array<ll,3> res;
res[0] = res[1] = 0;
res[2] = 1e18;
if(u == H) res[0] = 1;
if(is_village[u]) {
res[1] = 1;
res[2] = 0;
}
for(auto&& eid : adj[u]) {
auto [ut, vt, w] = edges[eid];
auto v = (ut != u ? ut : vt);
if(v == p || w == -1) continue;
auto t = dfs(v, u);
res[0] |= t[0];
res[1] |= t[1];
if(t[1]) res[2] = min(res[2], t[2] + w);
}
return res;
}
void solve() {
adj.assign(N, vector<int>());
is_village.assign(N, 0);
for(int i = 0; auto&& [x, y, z] : edges) {
adj[x].emplace_back(i);
adj[y].emplace_back(i);
++i;
}
for(auto&& v : villages) is_village[v] = 1;
for(auto&& [x, y] : QRS) {
auto t = get<2>(edges[x]);
get<2>(edges[x]) = -1;
auto tt = dfs(y);
get<2>(edges[x]) = t;
if(tt[0]) {
cout << "escaped\n";
} else if(tt[1]) {
cout << tt[2] << "\n";
} else {
cout << "oo\n";
}
}
}
};
template<typename Monoid>
struct SegTree {
using MX = Monoid;
using X = typename Monoid::X;
int n, log, size;
vector<X> dat;
SegTree() {}
template<typename F>
void build(int _n, F f) {
n = _n, log = 0;
while((1 << log) < n) ++log;
size = 1 << log;
dat.assign(size << 1, MX::unit());
for(int i = 0; i < n; ++i) dat[i] = f(i);
for(int i = size - 1; i >= 1; --i) update(i);
}
void set(int k, const X& x) {
assert(0 <= k && k < n);
dat[k += size] = x;
while(k >>= 1) update(k);
}
X prod(int l, int r) {
assert(0 <= l && l <= r && r <= n);
l += size, r += size;
X vl = MX::unit(), vr = MX::unit();
while(l < r) {
if(l & 1) vl = MX::op(vl, dat[l++]);
if(r & 1) vr = MX::op(dat[--r], vr);
l >>= 1, r >>= 1;
}
return MX::op(vl, vr);
}
void update(int k) { dat[k] = MX::op(dat[k << 1], dat[k << 1 | 1]); }
};
struct Monoid_1 {
using X = int;
using value_type = X;
static constexpr X op(const X& x, const X& y) noexcept { return x | y; }
static constexpr X unit() noexcept { return 0; }
};
namespace sub3 {
bool check() {
return S == N;
}
vector<vector<int>> adj;
vector<int> LID, RID, parent, V, head;
void dfs1(int u) {
auto& sz = RID;
sz[u] = 1;
int mx = 0;
for(auto& eid : adj[u]) {
auto&& [ut, vt, w] = edges[eid];
int v = (u != ut ? ut : vt);
if(v == parent[u]) continue;
parent[v] = u;
dfs1(v);
sz[u] += sz[v];
if(sz[v] > mx) {
mx = sz[v];
swap(eid, adj[u][0]);
}
}
}
void dfs2(int u, int& times) {
LID[u] = times++;
RID[u] += LID[u];
V[LID[u]] = u;
bool heavy = true;
for(auto&& eid : adj[u]) {
auto&& [ut, vt, w] = edges[eid];
int v = (u != ut ? ut : vt);
if(v == parent[u]) continue;
head[v] = (heavy ? head[u] : v);
heavy = false;
dfs2(v, times);
}
}
int LCA(int u, int v) {
for(int i = 25; i--; ) {
if(LID[u] > LID[v]) swap(u, v);
if(head[u] == head[v]) return u;
v = parent[head[v]];
}
assert(false);
}
vector<pair<int,int>> get_path_decomposition(int u, int v, bool edge = 0) {
vector<pair<int,int>> up, down;
while(true) {
if(head[u] == head[v]) break;
if(LID[u] < LID[v]) {
down.emplace_back(LID[head[v]], LID[v]);
v = parent[head[v]];
} else {
up.emplace_back(LID[u], LID[head[u]]);
u = parent[head[u]];
}
}
if(LID[u] < LID[v]) down.emplace_back(LID[u] + edge, LID[v]);
else if(LID[v] + edge <= LID[u]) up.emplace_back(LID[u], LID[v] + edge);
up.insert(up.end(), down.rbegin(), down.rend());
return up;
}
void solve() {
adj.assign(N, vector<int>());
LID.resize(N);
RID.resize(N);
parent.resize(N);
V.resize(N);
head.resize(N);
for(int i = 0; auto&& [x, y, z] : edges) {
adj[x].emplace_back(i);
adj[y].emplace_back(i);
++i;
}
parent[0] = -1;
dfs1(0);
int times = 0;
head[0] = 0;
dfs2(0, times);
SegTree<Monoid_1> seg;
seg.build(N, [](const int& i) { return 0; });
for(auto&& [x, y] : QRS) {
auto [ut, vt, w] = edges[x];
if(LID[ut] < LID[vt]) swap(ut, vt);
seg.set(LID[ut], 1);
//cout << LID[ut] << "\n";
bool fl = true;
auto pd = get_path_decomposition(H, y, 0);
for(auto&& [l, r] : pd) {
if(l > r) swap(l, r);
//cout << l << " " << r << "\n";
if(seg.prod(l, r + 1) != 0) {
fl = false;
break;
}
}
seg.set(LID[ut], 0);
if(fl) {
cout << "escaped\n";
} else {
cout << "0\n";
}
}
}
};
void solve() {
cin >> N >> S >> Q >> H;
--H;
edges.resize(N - 1);
QRS.resize(Q);
villages.resize(S);
for(auto& [u, v, w] : edges) {
cin >> u >> v >> w;
--u, --v;
}
for(auto& v : villages) {
cin >> v;
--v;
}
for(auto& [x, y] : QRS) {
cin >> x >> y;
--x, --y;
}
if(sub12::check()) return sub12::solve();
if(sub3::check()) return sub3::solve();
sub3::solve();
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
while(t--) solve();
}
Compilation message
valley.cpp: In function 'void sub12::solve()':
valley.cpp:37:20: warning: range-based 'for' loops with initializer only available with '-std=c++2a' or '-std=gnu++2a'
37 | for(int i = 0; auto&& [x, y, z] : edges) {
| ^~~~
valley.cpp: In function 'void sub3::solve()':
valley.cpp:167:20: warning: range-based 'for' loops with initializer only available with '-std=c++2a' or '-std=gnu++2a'
167 | for(int i = 0; auto&& [x, y, z] : edges) {
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
668 KB |
Output is correct |
| 2 |
Correct |
8 ms |
604 KB |
Output is correct |
| 3 |
Correct |
9 ms |
640 KB |
Output is correct |
| 4 |
Correct |
9 ms |
604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
668 KB |
Output is correct |
| 2 |
Correct |
8 ms |
604 KB |
Output is correct |
| 3 |
Correct |
9 ms |
640 KB |
Output is correct |
| 4 |
Correct |
9 ms |
604 KB |
Output is correct |
| 5 |
Correct |
6 ms |
348 KB |
Output is correct |
| 6 |
Correct |
7 ms |
572 KB |
Output is correct |
| 7 |
Correct |
14 ms |
604 KB |
Output is correct |
| 8 |
Correct |
5 ms |
348 KB |
Output is correct |
| 9 |
Correct |
7 ms |
344 KB |
Output is correct |
| 10 |
Correct |
14 ms |
600 KB |
Output is correct |
| 11 |
Correct |
6 ms |
348 KB |
Output is correct |
| 12 |
Correct |
7 ms |
580 KB |
Output is correct |
| 13 |
Correct |
14 ms |
604 KB |
Output is correct |
| 14 |
Correct |
12 ms |
588 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
89 ms |
16372 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
668 KB |
Output is correct |
| 2 |
Correct |
8 ms |
604 KB |
Output is correct |
| 3 |
Correct |
9 ms |
640 KB |
Output is correct |
| 4 |
Correct |
9 ms |
604 KB |
Output is correct |
| 5 |
Correct |
6 ms |
348 KB |
Output is correct |
| 6 |
Correct |
7 ms |
572 KB |
Output is correct |
| 7 |
Correct |
14 ms |
604 KB |
Output is correct |
| 8 |
Correct |
5 ms |
348 KB |
Output is correct |
| 9 |
Correct |
7 ms |
344 KB |
Output is correct |
| 10 |
Correct |
14 ms |
600 KB |
Output is correct |
| 11 |
Correct |
6 ms |
348 KB |
Output is correct |
| 12 |
Correct |
7 ms |
580 KB |
Output is correct |
| 13 |
Correct |
14 ms |
604 KB |
Output is correct |
| 14 |
Correct |
12 ms |
588 KB |
Output is correct |
| 15 |
Incorrect |
89 ms |
16372 KB |
Output isn't correct |
| 16 |
Halted |
0 ms |
0 KB |
- |
