| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 496454 |
2021-12-21T08:28:58 Z |
Ierus |
Valley (BOI19_valley) |
C++17 |
|
208 ms |
34036 KB |
#include<bits/stdc++.h>
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
*/
using namespace std;
#pragma GCC optimize ("unroll-loops,Ofast,O3")
#pragma GCC target("avx,avx2,fma")
#define F first
#define S second
#define sz(x) (int)x.size()
#define pb push_back
#define eb emplace_back
#define int long long
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define NFS ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
//#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
typedef long long ll;
const int E = 1e6+777;
const long long inf = 1e18+777;
const int N = 1e5+777;
const int MOD = 1e9+7;
const bool I = 1;
int n, s, q, e;
bool mag[N];
bitset<N> used;
int x[N], y[N], w[N];
struct D{
int v, w, id;
};
vector<D> g[N];
bool dfs(int v, int &pp, int p = 1){
// cerr << "v: " << v << '\n';
if(v == e){
return true;
}
used[v] = true;
bool res = false;
for(auto to : g[v]){
if(!used[to.v] && to.id != pp){
res |= dfs(to.v, pp, v);
}
}
return res;
}
int Find(int v, int pp){
int res = LLONG_MAX;
vector<int> d(n+1, LLONG_MAX);
set<pair<int,int>> st = {{d[v]=0,v}};
while(!st.empty()){
v = st.begin() -> S;
st.erase(st.begin());
if(mag[v]){
res = min(res, d[v]);
}
for(auto to : g[v]){
if(d[to.v] > d[v] + to.w && to.id != pp){
st.erase({d[to.v], to.v});
d[to.v] = d[v] + to.w;
st.insert({d[to.v], to.v});
}
}
}
return res;
}
const int LG = 19;
int up[N][LG+2], tin[N], tout[N], timer;
void dfs1(int v, int p = 0) {
tin[v] = ++timer;
up[v][0] = p;
for (int i = 1; i <= LG; ++i)
up[v][i] = up[up[v][i-1]][i-1];
for (auto to : g[v]) {
if (to.v != p)
dfs1(to.v, v);
}
tout[v] = timer;
}
bool upper(int a, int b) {
return tin[a] <= tin[b] && tout[b] <= tout[a] ;
}
int lca (int a, int b) {
if (upper (a, b)) return a;
if (upper (b, a)) return b;
for (int i = LG; i>=0; --i)
if (!upper(up[a][i], b))
a = up[a][i];
return up[a][0];
}
signed main(){NFS;
cin >> n >> s >> q >> e;
for(int i = 1; i < n; ++i){
cin >> x[i] >> y[i] >> w[i];
g[x[i]].pb({y[i], w[i], i});
g[y[i]].pb({x[i], w[i], i});
}
for(int i = 1; i <= s; ++i){
int xx; cin >> xx;
mag[xx] = true;
}
// if(n <= 1000 && q <= 10000){
// for(int i = 1; i <= q; ++i){
// int pp, h;
// cin >> pp >> h;
// used.reset();
// if(dfs(h, pp)){
// cout << "escaped\n";
// }else{
// int cur = Find(h, pp);
// if(cur == LLONG_MAX) cout << "oo\n";
// else cout << cur << '\n';
// }
// }
// exit(false);
// }
dfs1(1, 1);
for(int i = 1; i <= q; ++i){
int pp, h;
cin >> pp >> h;
int lc = lca(h, e);
if((lca(e, x[pp]) == x[pp] && lca(x[pp], lc) == lc) && (lca(e, y[pp]) == y[pp] && lca(y[pp], lc) == lc)){
cout << "0\n";
continue;
}
if((lca(h, x[pp]) == x[pp] && lca(x[pp], lc) == lc) && (lca(h, y[pp]) == y[pp] && lca(y[pp], lc) == lc)){
cout << "0\n";
continue;
}
cout << "escaped\n";
}
}
/*
10 10 5 4
7 2 3
4 8 3
9 10 1
6 7 3
9 2 3
10 1 2
8 2 2
5 2 1
3 8 2
1 2 3 4 5 6 7 8 9 10
2 1
1 5
8 4
6 2
7 7
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
2684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
2684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
146 ms |
30132 KB |
Output is correct |
| 2 |
Correct |
152 ms |
30168 KB |
Output is correct |
| 3 |
Correct |
173 ms |
30292 KB |
Output is correct |
| 4 |
Correct |
208 ms |
31676 KB |
Output is correct |
| 5 |
Correct |
176 ms |
31556 KB |
Output is correct |
| 6 |
Correct |
148 ms |
34036 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
2684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
