| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 261445 | 2020-08-11T18:02:27 Z | CSQ31 | Valley (BOI19_valley) | C++14 | 236 ms | 49148 KB |
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define MOD (ll)(998244353)
#define INF (ll)(1e18)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
int gcd(int A,int B) {if(!B)return A;return gcd(B,A%B);}
const int MAXN = 1e5+5;
ll n,s,q,e;
vector<vector<PII>> adj(MAXN);
vector<bool>shop(MAXN,0);
ll par[21][MAXN];
ll mn[21][MAXN];
ll sub[MAXN];
ll depth[MAXN];
ll depthw[MAXN];
ll tin[MAXN];
ll tout[MAXN];
ll timer = 0;
void dfs(int v,int u = 0)
{
sub[v] = INF;
if(shop[v])sub[v] = depthw[v];
tin[v] = ++timer;
for(auto x:adj[v]){
int to = x.fi;
ll w = x.se;
if(to == u)continue;
depth[to] = depth[v]+1;
depthw[to] = depthw[v]+w;
dfs(to,v);
sub[v] = min(sub[v],sub[to]);
}
tout[v] = timer;
par[0][v] = u;
if(sub[v] == INF)mn[0][v] = INF;
else mn[0][v] = sub[v]-2*depthw[v];
}
bool chk(int v,int u)
{
return (tin[v] >= tin[u] && tout[u] >= tout[v]);
}
ll query(int blk,int v)
{
int tmp = depth[v]-depth[blk]+1;
ll ans = INF;
for(int j=0;tmp;j++,tmp>>=1){
if(tmp&1){
ans = min(ans,mn[j][v]);
v = par[j][v];
}
}
return ans;
}
int main()
{
owo
cin>>n>>s>>q>>e;
vector<pii>edge(n+1);
for(int i=1;i<n;i++){
ll v,u,w;
cin>>v>>u>>w;
adj[v].pb({u,w});
adj[u].pb({v,w});
edge[i] = {v,u};
}
while(s--){
int c;cin>>c;
shop[c] = 1;
}
dfs(e);
for(int i=1;i<n;i++){
int v = edge[i].fi;
int u = edge[i].se;
if(depth[u] > depth[v])swap(v,u);
edge[i] = {v,u};
}
for(int k=1;k<=20;k++){
for(int i=1;i<=n;i++){
int jump = par[k-1][i];
par[k][i] = par[k-1][jump];
mn[k][i] = min(mn[k-1][i],mn[k-1][jump]);
}
}
while(q--){
int i,r;
cin>>i>>r;
int v = edge[i].fi;
if(!chk(r,v))cout<<"escaped"<<'\n';
else{
ll ans = query(v,r);
if(ans >= INF)cout<<"oo"<<'\n';
else cout<<ans+depthw[r]<<'\n';
}
}
}
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 5 ms | 3072 KB | Output is correct |
| 2 | Correct | 5 ms | 3072 KB | Output is correct |
| 3 | Correct | 5 ms | 3072 KB | Output is correct |
| 4 | Correct | 5 ms | 3072 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 5 ms | 3072 KB | Output is correct |
| 2 | Correct | 5 ms | 3072 KB | Output is correct |
| 3 | Correct | 5 ms | 3072 KB | Output is correct |
| 4 | Correct | 5 ms | 3072 KB | Output is correct |
| 5 | Correct | 3 ms | 3328 KB | Output is correct |
| 6 | Correct | 3 ms | 3328 KB | Output is correct |
| 7 | Correct | 4 ms | 3456 KB | Output is correct |
| 8 | Correct | 3 ms | 3328 KB | Output is correct |
| 9 | Correct | 5 ms | 3328 KB | Output is correct |
| 10 | Correct | 3 ms | 3456 KB | Output is correct |
| 11 | Correct | 4 ms | 3328 KB | Output is correct |
| 12 | Correct | 3 ms | 3328 KB | Output is correct |
| 13 | Correct | 4 ms | 3456 KB | Output is correct |
| 14 | Correct | 3 ms | 3456 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 175 ms | 46152 KB | Output is correct |
| 2 | Correct | 200 ms | 46072 KB | Output is correct |
| 3 | Correct | 190 ms | 46104 KB | Output is correct |
| 4 | Correct | 209 ms | 47100 KB | Output is correct |
| 5 | Correct | 193 ms | 47348 KB | Output is correct |
| 6 | Correct | 236 ms | 48376 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 5 ms | 3072 KB | Output is correct |
| 2 | Correct | 5 ms | 3072 KB | Output is correct |
| 3 | Correct | 5 ms | 3072 KB | Output is correct |
| 4 | Correct | 5 ms | 3072 KB | Output is correct |
| 5 | Correct | 3 ms | 3328 KB | Output is correct |
| 6 | Correct | 3 ms | 3328 KB | Output is correct |
| 7 | Correct | 4 ms | 3456 KB | Output is correct |
| 8 | Correct | 3 ms | 3328 KB | Output is correct |
| 9 | Correct | 5 ms | 3328 KB | Output is correct |
| 10 | Correct | 3 ms | 3456 KB | Output is correct |
| 11 | Correct | 4 ms | 3328 KB | Output is correct |
| 12 | Correct | 3 ms | 3328 KB | Output is correct |
| 13 | Correct | 4 ms | 3456 KB | Output is correct |
| 14 | Correct | 3 ms | 3456 KB | Output is correct |
| 15 | Correct | 175 ms | 46152 KB | Output is correct |
| 16 | Correct | 200 ms | 46072 KB | Output is correct |
| 17 | Correct | 190 ms | 46104 KB | Output is correct |
| 18 | Correct | 209 ms | 47100 KB | Output is correct |
| 19 | Correct | 193 ms | 47348 KB | Output is correct |
| 20 | Correct | 236 ms | 48376 KB | Output is correct |
| 21 | Correct | 172 ms | 46200 KB | Output is correct |
| 22 | Correct | 164 ms | 45944 KB | Output is correct |
| 23 | Correct | 166 ms | 46116 KB | Output is correct |
| 24 | Correct | 186 ms | 47352 KB | Output is correct |
| 25 | Correct | 204 ms | 49148 KB | Output is correct |
| 26 | Correct | 153 ms | 46200 KB | Output is correct |
| 27 | Correct | 160 ms | 45944 KB | Output is correct |
| 28 | Correct | 169 ms | 46200 KB | Output is correct |
| 29 | Correct | 187 ms | 47096 KB | Output is correct |
| 30 | Correct | 223 ms | 48056 KB | Output is correct |
| 31 | Correct | 156 ms | 46328 KB | Output is correct |
| 32 | Correct | 164 ms | 46072 KB | Output is correct |
| 33 | Correct | 175 ms | 46328 KB | Output is correct |
| 34 | Correct | 193 ms | 47352 KB | Output is correct |
| 35 | Correct | 199 ms | 48888 KB | Output is correct |
| 36 | Correct | 190 ms | 47864 KB | Output is correct |