oj.uz

Submission #337798

# Submission time Handle Problem Language Result Execution time Memory
337798 2020-12-21T17:03:43 Z Thistle Factories (JOI14_factories) C++14
100 / 100
 5146 ms 250296 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define all(a) a.begin(),a.end()
#define vec vector
#define pb push_back
#define rng(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) rng(i,0,n)
#define siz(a) a.size()
template<typename T>
void chmin(T& a,T b){a=min(a,b);}
template<typename T>
void chmax(T& a,T b){a=max(a,b);}

int n;
vec<int>e[600000];
ll dpt[600000];
vec<int>eul;
vec<ll>dpto;
int out[600000];
int spt[1100000][20];
int lgt[1100000];
bool se[600000],se2[600000];

int lca(int a,int b){
  int x=out[a],y=out[b];
  if(x>y) swap(x,y);
  int k=lgt[(y-x+1)];
  int s=spt[x][k],t=spt[y-(1<<k)+1][k];
  if(dpto[s]<dpto[t]) return eul[s];
  else return eul[t];
}
ll dist(int a,int b){
  return dpt[a]+dpt[b]-2*dpt[lca(a,b)];
}

void Init(int N, int A[], int B[], int D[]) {
  n=N;
  map<pair<int, int>, ll>mp;
  rep(i,n-1){
    e[A[i]].pb(B[i]);
    e[B[i]].pb(A[i]);
    mp[make_pair(min(A[i],B[i]),max(A[i],B[i]))]=D[i];
  }
  
  auto dfs=[&](int x,int p,ll d,auto& dfs)->void{
    dpt[x]=d;
    out[x]=siz(eul);
    eul.pb(x);dpto.pb(d);
    for(auto g:e[x]){
      if(g==p) continue;
      ll k=mp[make_pair(min(x,g),max(x,g))];
      dfs(g,x,d+k,dfs);
      eul.pb(x);dpto.pb(d);
    }
  };
  dfs(0,-1,0,dfs);
  
  rep(i,siz(eul)) spt[i][0]=i;
  rng(i,2,siz(eul)+1) lgt[i]=lgt[i>>1]+1;

  rep(j,19) for(int i=0;i+(1<<(j+1))<=siz(eul);i++){
    int a=spt[i][j],b=spt[i+(1<<j)][j];
    if(dpto[a]<dpto[b]) spt[i][j+1]=a;
    else spt[i][j+1]=b;
  }
}

long long Query(int S, int X[], int T, int Y[]) {
  constexpr ll inf=1e17;
  ll ans=inf;
  vec<int>v;
  rep(i,S){
    v.pb(X[i]);
    se[X[i]]=1;
  }
  rep(i,T) {
    v.pb(Y[i]);
    se2[Y[i]]=1;
  }
  sort(all(v),[&](int& a,int& b){
    return out[a]<out[b];
  });
  int sz=v.size();
  rep(i,sz-1){
    v.pb(lca(v[i],v[i+1]));
  }
  sort(all(v));v.erase(unique(all(v)),v.end());
  sort(all(v),[&](int& a,int& b){
    return out[a]<out[b];
  });


  stack<int>st;
  vec<vec<int>>f(siz(v),vec<int>());
  rep(i,v.size()){
    while(!st.empty()&&dist(v[st.top()],v[i])!=dpt[v[i]]-dpt[v[st.top()]]){
      st.pop();
    }
    if(!st.empty()) f[st.top()].pb(i);
    st.push(i);
  }

  vec<ll>dst(v.size(),inf);
  auto dfs=[&](int x,auto& dfs)->ll{
    ll ret=inf;
    if(se[v[x]]) ret=0;
    for(auto g:f[x]){
      chmin(ret,dfs(g,dfs)+dpt[v[g]]-dpt[v[x]]);
    }
    return dst[x]=ret;
  };
  dfs(0,dfs);
  auto rec=[&](int x,ll near,auto&rec)->void{
    chmin(near,dst[x]);
    if(se2[v[x]]) chmin(ans,near);
    for(auto g:f[x]){
      rec(g,near+dpt[v[g]]-dpt[v[x]],rec);
    }
  };
  rec(0,inf,rec);

  rep(i,S)se[X[i]]=0;
  rep(i,T)se2[Y[i]]=0;
  return ans;
}

Compilation message

factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:8:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define rng(i,a,b) for(int i=(a);i<(b);i++)
      |                                   ^
factories.cpp:9:18: note: in expansion of macro 'rng'
    9 | #define rep(i,n) rng(i,0,n)
      |                  ^~~
factories.cpp:60:3: note: in expansion of macro 'rep'
   60 |   rep(i,siz(eul)) spt[i][0]=i;
      |   ^~~
factories.cpp:8:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define rng(i,a,b) for(int i=(a);i<(b);i++)
      |                                   ^
factories.cpp:61:3: note: in expansion of macro 'rng'
   61 |   rng(i,2,siz(eul)+1) lgt[i]=lgt[i>>1]+1;
      |   ^~~
factories.cpp:63:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |   rep(j,19) for(int i=0;i+(1<<(j+1))<=siz(eul);i++){
      |                                     ^
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:8:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define rng(i,a,b) for(int i=(a);i<(b);i++)
      |                                   ^
factories.cpp:9:18: note: in expansion of macro 'rng'
    9 | #define rep(i,n) rng(i,0,n)
      |                  ^~~
factories.cpp:97:3: note: in expansion of macro 'rep'
   97 |   rep(i,v.size()){
      |   ^~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 15084 KB Output is correct
2 Correct 1250 ms 24684 KB Output is correct
3 Correct 1387 ms 33900 KB Output is correct
4 Correct 1301 ms 34028 KB Output is correct
5 Correct 1103 ms 34156 KB Output is correct
6 Correct 829 ms 33772 KB Output is correct
7 Correct 1356 ms 33756 KB Output is correct
8 Correct 1296 ms 34028 KB Output is correct
9 Correct 1107 ms 34284 KB Output is correct
10 Correct 830 ms 33772 KB Output is correct
11 Correct 1359 ms 33900 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14828 KB Output is correct
2 Correct 2843 ms 175800 KB Output is correct
3 Correct 3048 ms 181176 KB Output is correct
4 Correct 2589 ms 180428 KB Output is correct
5 Correct 2657 ms 229480 KB Output is correct
6 Correct 3190 ms 182344 KB Output is correct
7 Correct 2282 ms 57348 KB Output is correct
8 Correct 1424 ms 58204 KB Output is correct
9 Correct 1328 ms 63876 KB Output is correct
10 Correct 2173 ms 58656 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 15084 KB Output is correct
2 Correct 1250 ms 24684 KB Output is correct
3 Correct 1387 ms 33900 KB Output is correct
4 Correct 1301 ms 34028 KB Output is correct
5 Correct 1103 ms 34156 KB Output is correct
6 Correct 829 ms 33772 KB Output is correct
7 Correct 1356 ms 33756 KB Output is correct
8 Correct 1296 ms 34028 KB Output is correct
9 Correct 1107 ms 34284 KB Output is correct
10 Correct 830 ms 33772 KB Output is correct
11 Correct 1359 ms 33900 KB Output is correct
12 Correct 13 ms 14828 KB Output is correct
13 Correct 2843 ms 175800 KB Output is correct
14 Correct 3048 ms 181176 KB Output is correct
15 Correct 2589 ms 180428 KB Output is correct
16 Correct 2657 ms 229480 KB Output is correct
17 Correct 3190 ms 182344 KB Output is correct
18 Correct 2282 ms 57348 KB Output is correct
19 Correct 1424 ms 58204 KB Output is correct
20 Correct 1328 ms 63876 KB Output is correct
21 Correct 2173 ms 58656 KB Output is correct
22 Correct 4614 ms 206344 KB Output is correct
23 Correct 4291 ms 209280 KB Output is correct
24 Correct 5097 ms 211256 KB Output is correct
25 Correct 4762 ms 215692 KB Output is correct
26 Correct 5146 ms 206928 KB Output is correct
27 Correct 4362 ms 250296 KB Output is correct
28 Correct 3389 ms 210636 KB Output is correct
29 Correct 4898 ms 206360 KB Output is correct
30 Correct 4868 ms 205044 KB Output is correct
31 Correct 4859 ms 206056 KB Output is correct
32 Correct 2004 ms 81444 KB Output is correct
33 Correct 1482 ms 73184 KB Output is correct
34 Correct 2300 ms 67084 KB Output is correct
35 Correct 2256 ms 67040 KB Output is correct
36 Correct 2605 ms 68152 KB Output is correct
37 Correct 2596 ms 68068 KB Output is correct