oj.uz

Submission #335951

# Submission time Handle Problem Language Result Execution time Memory
335951 2020-12-14T11:30:18 Z Thistle Factories (JOI14_factories) C++14
15 / 100
 8000 ms 233588 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[1300000][20];
int lgt[1300000];
int id[1300000];
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 53 ms 29036 KB Output is correct
2 Correct 2146 ms 38252 KB Output is correct
3 Correct 2877 ms 38252 KB Output is correct
4 Correct 2172 ms 38380 KB Output is correct
5 Correct 3474 ms 38888 KB Output is correct
6 Correct 635 ms 38124 KB Output is correct
7 Correct 2792 ms 38232 KB Output is correct
8 Correct 2797 ms 38300 KB Output is correct
9 Correct 3577 ms 38884 KB Output is correct
10 Correct 676 ms 38252 KB Output is correct
11 Correct 2811 ms 38604 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 28908 KB Output is correct
2 Correct 4771 ms 179992 KB Output is correct
3 Correct 7322 ms 186552 KB Output is correct
4 Correct 1798 ms 176704 KB Output is correct
5 Execution timed out 8068 ms 233588 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 29036 KB Output is correct
2 Correct 2146 ms 38252 KB Output is correct
3 Correct 2877 ms 38252 KB Output is correct
4 Correct 2172 ms 38380 KB Output is correct
5 Correct 3474 ms 38888 KB Output is correct
6 Correct 635 ms 38124 KB Output is correct
7 Correct 2792 ms 38232 KB Output is correct
8 Correct 2797 ms 38300 KB Output is correct
9 Correct 3577 ms 38884 KB Output is correct
10 Correct 676 ms 38252 KB Output is correct
11 Correct 2811 ms 38604 KB Output is correct
12 Correct 27 ms 28908 KB Output is correct
13 Correct 4771 ms 179992 KB Output is correct
14 Correct 7322 ms 186552 KB Output is correct
15 Correct 1798 ms 176704 KB Output is correct
16 Execution timed out 8068 ms 233588 KB Time limit exceeded
17 Halted 0 ms 0 KB -