oj.uz

Submission #203699

# Submission time Handle Problem Language Result Execution time Memory
203699 2020-02-21T21:36:05 Z imaxblue Valley (BOI19_valley) C++17
9 / 100
 3000 ms 51192 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define x first
#define y second
#define pii pair<int, int>
#define p3i pair<pii, int>
#define pll pair<ll, ll>
#define p3l pair<pll, ll>
#define vi vector<int>
#define vpii vector<pii>
#define vp3i vector<p3i>
#define vpll vector<pll>
#define vp3l vector<p3l>
#define lseg L, (L+R)/2, N*2+1
#define rseg (L+R)/2+1, R, N*2+2
#define ub upper_bound
#define lb lower_bound
#define pq priority_queue
#define MN 1000000007
#define fox(k, x) for (int k=0; k<x; ++k)
#define fox1(k, x) for (int k=1; k<=x; ++k)
#define foxr(k, x) for (int k=x-1; k>=0; --k)
#define fox1r(k, x) for (int k=x; k>0; --k)
#define ms multiset
#define flood(x) memset(x, 0x3f3f3f3f, sizeof x)
#define drain(x) memset(x, 0, sizeof x)
#define rng() ((rand() << 14)+rand())
#define scan(X) do{while((X=getchar())<'0'); for(X-='0'; '0'<=(_=getchar()); X=(X<<3)+(X<<1)+_-'0');}while(0)
char _;
#define pi 3.14159265358979323846
#define startrng mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n, q, s, e, a, b, w;
bool g[100005];
int sp[100005][20], sp2[100050][20], d[100005], off[100005];
ll best[100005], dis[100005][20];
vector<pii> v[100005];
vector<int> v2[100005];
void dfs1(int N, int P){
  best[N]=(g[N]?0:(1LL<<60));
  for(auto i:v[N]){
    if (i.x==P) continue;
    dfs1(i.x, N);
    best[N]=min(best[N], best[i.x]+i.y);
  }
}
void dfs2(int N, int P, int D, int W){
  off[W]=N;
  d[N] = d[P]+1;
  sp[N][0]=P;
  sp2[N][0]=P; dis[N][0]=D;
  int k=17;
  int TP=sp2[N][0];
  while(TP!=0 && best[TP]+dis[N][0]>=best[N]){
    while(k>0 && (sp2[TP][k]==0 || best[sp2[TP][k]]+dis[TP][k]+dis[N][0]<best[N])){
      --k;
    }
    dis[N][0]+=dis[TP][k];
    TP = sp2[TP][k];
  }
  sp2[N][0]=TP;
  fox1(l, 18){
    sp[N][l] = sp[sp[N][l-1]][0];
    sp2[N][l] = sp2[sp2[N][l-1]][0];
    dis[N][l] = dis[N][l-1] + dis[sp2[N][l-1]][l-1];
  }
  fox(l, v[N].size()){
    pii i=v[N][l];
    if (i.x==P) continue;
    dfs2(i.x, N, i.y, v2[N][l]);
  }
}
int lca(int A, int B){
  int k=17;
  while(d[A]>d[B]){
    while(d[A]-(1<<k)<d[B]) --k;
    A=sp[A][k];
  }
  while(d[B]>d[A]){
    while(d[B]-(1<<k)<d[A]) --k;
    B=sp[B][k];
  }
  k=17;
  while(A!=B){
    while(k>0 && (sp[A][k]==sp[B][k])) --k;
    A=sp[A][k];
    B=sp[B][k];
  }
  return A;
}
ll get(int A, int B){
  ll D=0;
  int k=17;
  while(d[sp2[A][0]]>=d[B]){
    while(k>0 && d[sp2[A][k]]<d[B]) --k;
    D+=dis[A][k];
    A=sp2[A][k];
  }
  return D+best[A];
}
int32_t main(){
  scanf("%i%i%i%i", &n, &s, &q, &e);
  fox1(l, n-1){
    scanf("%i%i%i", &a, &b, &w);
    v[a].pb(mp(b, w));
    v[b].pb(mp(a, w));
    v2[a].pb(l);
    v2[b].pb(l);
  }
  fox(l, s){
    scanf("%i", &a);
    g[a]=1;
  }
  dfs1(e, 0);
  dfs2(e, 0, 0, 0);
  while(q--){
    scanf("%i%i", &b, &a);
    b=off[b];
    if (lca(a, b)!=b){
      printf("escaped\n");
      continue;
    }
    ll t = get(a, b);
    if (t>=(1LL<<60)){
      printf("oo\n");
    } else {
      printf("%lli\n", t);
    }
  }
  return 0;
}

Compilation message

valley.cpp: In function 'void dfs2(int, int, int, int)':
valley.cpp:23:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(k, x) for (int k=0; k<x; ++k)
valley.cpp:70:7:
   fox(l, v[N].size()){
       ~~~~~~~~~~~~~~              
valley.cpp:70:3: note: in expansion of macro 'fox'
   fox(l, v[N].size()){
   ^~~
valley.cpp: In function 'int32_t main()':
valley.cpp:105:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i%i%i%i", &n, &s, &q, &e);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:107:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i%i%i", &a, &b, &w);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
valley.cpp:114:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i", &a);
     ~~~~~^~~~~~~~~~
valley.cpp:120:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i%i", &b, &a);
     ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 5240 KB Output is correct
2 Correct 12 ms 5240 KB Output is correct
3 Correct 12 ms 5240 KB Output is correct
4 Correct 12 ms 5240 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 5240 KB Output is correct
2 Correct 12 ms 5240 KB Output is correct
3 Correct 12 ms 5240 KB Output is correct
4 Correct 12 ms 5240 KB Output is correct
5 Correct 10 ms 5496 KB Output is correct
6 Correct 9 ms 5496 KB Output is correct
7 Correct 10 ms 5500 KB Output is correct
8 Correct 9 ms 5496 KB Output is correct
9 Correct 9 ms 5496 KB Output is correct
10 Incorrect 9 ms 5496 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 50040 KB Output is correct
2 Correct 287 ms 49400 KB Output is correct
3 Correct 316 ms 49144 KB Output is correct
4 Correct 1552 ms 51192 KB Output is correct
5 Execution timed out 3030 ms 50808 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 5240 KB Output is correct
2 Correct 12 ms 5240 KB Output is correct
3 Correct 12 ms 5240 KB Output is correct
4 Correct 12 ms 5240 KB Output is correct
5 Correct 10 ms 5496 KB Output is correct
6 Correct 9 ms 5496 KB Output is correct
7 Correct 10 ms 5500 KB Output is correct
8 Correct 9 ms 5496 KB Output is correct
9 Correct 9 ms 5496 KB Output is correct
10 Incorrect 9 ms 5496 KB Output isn't correct
11 Halted 0 ms 0 KB -