oj.uz

Submission #335950

# Submission time Handle Problem Language Result Execution time Memory
335950 2020-12-14T11:28:15 Z Thistle Factories (JOI14_factories) C++14
15 / 100
 3507 ms 277364 KB 
#pragma GCC target("avx2")
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include "factories.h"


using namespace std;
using ll=long long;
using H=pair<ll, ll>;
#define fs first
#define sc second
#define rng(i,a,b) for(ll i=(a);i<(b);i++)
#define rep(i,n) rng(i,0,n)
#define vec vector
#define siz(a) (a.size())
#define pb push_back
template<typename T>
void chmax(T &a,T b){a=max(a,b);}
template<typename T>
void chmin(T &a,T b){a=min(a,b);}

constexpr ll inf=1e17;

int n;
ll dpt[600000],dpt2[600000];
int pa[600000];
vec<bool>dead;
int root;
vec<int>tree[600000];
int par[600000];
vec<H>e[600000];
vec<int>eul,out;
int spt[600000][20];
int lgt[600000];
int id[600000];
ll lca2(int x,int y){
  ll ret=0;
  x=id[x],y=id[y];
  if(x>y) swap(x,y);
  int k=lgt[y-x];
  x=spt[x][k];
  y=spt[y-(1<<k)+1][k];
  if(eul[spt[x][0]]<eul[spt[y][0]]) return out[spt[x][0]];
  else return out[spt[y][0]];
}
ll lca(int x,int y){
  int k=lca2(x,y);
  return dpt[x]+dpt[y]-2*dpt[k];
}
int octr(int x){
  static int sz[600000];
  auto rec=[&](int pos,int p, auto& rec)->void{
    sz[pos]=1;
    for(auto g:e[pos]){
      if(g.fs==p||dead[g.fs]) continue;
      rec(g.fs,pos,rec);
      sz[pos]+=sz[g.fs];
    }
  };
  rec(x,-1,rec);
  int N=sz[x];
  auto dfs=[&](int pos,int p,auto& dfs)->int{
    for(auto g:e[pos]){
      if(g.fs==p||dead[g.fs]) continue;
      if(sz[g.fs]>N/2) return dfs(g.fs,pos,dfs);
    }
    return pos;
  };
  return dfs(x,-1,dfs);
}
int build(int x){
  int c=octr(x);
  dead[c]=1;
  if(root==-1) root=c;
  for(auto g:e[c]){
    if(dead[g.fs])continue;
    int k=build(g.fs);
    tree[c].pb(k);
    par[k]=c;
  }
  return c;
}

void Init(int N, int A[], int B[], int D[]) {
  n=N;
  rep(i,n-1){
    e[A[i]].pb(H{B[i],D[i]});
    e[B[i]].pb(H{A[i],D[i]});
  }
  auto dfs=[&](int x,int p,ll d,int d2,auto& dfs)->void{
    dpt[x]=d,pa[x]=p,dpt2[x]=d2;
    for(auto g:e[x]){
      if(g.fs==p) continue;
      eul.pb(dpt2[x]);out.pb(x);
      dfs(g.fs, x, d+g.sc,d2+1, dfs);
    }
    id[x]=siz(eul);
    eul.pb(dpt2[x]);out.pb(x);
  };
  dfs(0,-1,0,0,dfs);


  rep(i,siz(eul)) spt[i][0]=i;
  rng(i,2,siz(eul)+2) lgt[i]=lgt[i>>1]+1;

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


  root=-1;
  dead.assign(n,false);
  build(0);
}

long long Query(int S, int X[], int T, int Y[]) {
  ll ans=inf;
  map<int, ll>mp;
  rep(i,S){
    int t=X[i]; mp[t]=0;
    do{
      t=par[t];
      if(mp.find(t)==mp.end()) mp[t]=lca(t,X[i]);
      else chmin(mp[t],lca(t,X[i]));
    }while(t!=root);
  }
  rep(i,T){
    int t=Y[i];
    if(mp.find(t)!=mp.end()) chmin(ans,mp[t]);
    do{
      t=par[t];
      if(mp.find(t)!=mp.end()) chmin(ans,lca(Y[i],t)+mp[t]);
    }while(t!=root);
  }
  return ans;
}

Compilation message

factories.cpp: In function 'll lca2(int, int)':
factories.cpp:37:6: warning: unused variable 'ret' [-Wunused-variable]
   37 |   ll ret=0;
      |      ^~~
factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:12:34: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define rng(i,a,b) for(ll i=(a);i<(b);i++)
      |                                  ^
factories.cpp:13:18: note: in expansion of macro 'rng'
   13 | #define rep(i,n) rng(i,0,n)
      |                  ^~~
factories.cpp:103:3: note: in expansion of macro 'rep'
  103 |   rep(i,siz(eul)) spt[i][0]=i;
      |   ^~~
factories.cpp:12:34: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define rng(i,a,b) for(ll i=(a);i<(b);i++)
      |                                  ^
factories.cpp:104:3: note: in expansion of macro 'rng'
  104 |   rng(i,2,siz(eul)+2) lgt[i]=lgt[i>>1]+1;
      |   ^~~
factories.cpp:106:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |   rep(i,19)for(int j=0;j+(1<<i)<=siz(eul);j++){
      |                                ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 29036 KB Output is correct
2 Correct 2139 ms 40812 KB Output is correct
3 Correct 2922 ms 40684 KB Output is correct
4 Correct 2173 ms 40940 KB Output is correct
5 Correct 3507 ms 41324 KB Output is correct
6 Correct 635 ms 40556 KB Output is correct
7 Correct 2808 ms 40848 KB Output is correct
8 Correct 2751 ms 40940 KB Output is correct
9 Correct 3468 ms 41324 KB Output is correct
10 Correct 655 ms 40684 KB Output is correct
11 Correct 2835 ms 40716 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 28780 KB Output is correct
2 Runtime error 1163 ms 277364 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 29036 KB Output is correct
2 Correct 2139 ms 40812 KB Output is correct
3 Correct 2922 ms 40684 KB Output is correct
4 Correct 2173 ms 40940 KB Output is correct
5 Correct 3507 ms 41324 KB Output is correct
6 Correct 635 ms 40556 KB Output is correct
7 Correct 2808 ms 40848 KB Output is correct
8 Correct 2751 ms 40940 KB Output is correct
9 Correct 3468 ms 41324 KB Output is correct
10 Correct 655 ms 40684 KB Output is correct
11 Correct 2835 ms 40716 KB Output is correct
12 Correct 25 ms 28780 KB Output is correct
13 Runtime error 1163 ms 277364 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Halted 0 ms 0 KB -