| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 348621 | 2021-01-15T09:48:17 Z | Nima_Naderi | Valley (BOI19_valley) | C++14 | 223 ms | 54508 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
for(int k=0;k<=20;k++)mn[k][0] = INF;
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';
}
}
}
//codam paride az cms
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 5 ms | 3180 KB | Output is correct |
| 2 | Correct | 5 ms | 3180 KB | Output is correct |
| 3 | Correct | 5 ms | 3180 KB | Output is correct |
| 4 | Correct | 6 ms | 3180 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 5 ms | 3180 KB | Output is correct |
| 2 | Correct | 5 ms | 3180 KB | Output is correct |
| 3 | Correct | 5 ms | 3180 KB | Output is correct |
| 4 | Correct | 6 ms | 3180 KB | Output is correct |
| 5 | Correct | 3 ms | 3436 KB | Output is correct |
| 6 | Correct | 3 ms | 3436 KB | Output is correct |
| 7 | Correct | 3 ms | 3436 KB | Output is correct |
| 8 | Correct | 3 ms | 3436 KB | Output is correct |
| 9 | Correct | 4 ms | 3436 KB | Output is correct |
| 10 | Correct | 3 ms | 3436 KB | Output is correct |
| 11 | Correct | 4 ms | 3436 KB | Output is correct |
| 12 | Correct | 3 ms | 3436 KB | Output is correct |
| 13 | Correct | 3 ms | 3436 KB | Output is correct |
| 14 | Correct | 3 ms | 3436 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 159 ms | 50020 KB | Output is correct |
| 2 | Correct | 163 ms | 49772 KB | Output is correct |
| 3 | Correct | 176 ms | 50048 KB | Output is correct |
| 4 | Correct | 196 ms | 51820 KB | Output is correct |
| 5 | Correct | 177 ms | 52076 KB | Output is correct |
| 6 | Correct | 223 ms | 54124 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 5 ms | 3180 KB | Output is correct |
| 2 | Correct | 5 ms | 3180 KB | Output is correct |
| 3 | Correct | 5 ms | 3180 KB | Output is correct |
| 4 | Correct | 6 ms | 3180 KB | Output is correct |
| 5 | Correct | 3 ms | 3436 KB | Output is correct |
| 6 | Correct | 3 ms | 3436 KB | Output is correct |
| 7 | Correct | 3 ms | 3436 KB | Output is correct |
| 8 | Correct | 3 ms | 3436 KB | Output is correct |
| 9 | Correct | 4 ms | 3436 KB | Output is correct |
| 10 | Correct | 3 ms | 3436 KB | Output is correct |
| 11 | Correct | 4 ms | 3436 KB | Output is correct |
| 12 | Correct | 3 ms | 3436 KB | Output is correct |
| 13 | Correct | 3 ms | 3436 KB | Output is correct |
| 14 | Correct | 3 ms | 3436 KB | Output is correct |
| 15 | Correct | 159 ms | 50020 KB | Output is correct |
| 16 | Correct | 163 ms | 49772 KB | Output is correct |
| 17 | Correct | 176 ms | 50048 KB | Output is correct |
| 18 | Correct | 196 ms | 51820 KB | Output is correct |
| 19 | Correct | 177 ms | 52076 KB | Output is correct |
| 20 | Correct | 223 ms | 54124 KB | Output is correct |
| 21 | Correct | 145 ms | 49388 KB | Output is correct |
| 22 | Correct | 157 ms | 49388 KB | Output is correct |
| 23 | Correct | 163 ms | 49388 KB | Output is correct |
| 24 | Correct | 184 ms | 51564 KB | Output is correct |
| 25 | Correct | 194 ms | 54508 KB | Output is correct |
| 26 | Correct | 140 ms | 49388 KB | Output is correct |
| 27 | Correct | 156 ms | 49260 KB | Output is correct |
| 28 | Correct | 166 ms | 49388 KB | Output is correct |
| 29 | Correct | 189 ms | 50924 KB | Output is correct |
| 30 | Correct | 211 ms | 52588 KB | Output is correct |
| 31 | Correct | 144 ms | 49516 KB | Output is correct |
| 32 | Correct | 160 ms | 49388 KB | Output is correct |
| 33 | Correct | 166 ms | 49644 KB | Output is correct |
| 34 | Correct | 190 ms | 51436 KB | Output is correct |
| 35 | Correct | 193 ms | 54380 KB | Output is correct |
| 36 | Correct | 174 ms | 51564 KB | Output is correct |