Submission #653219

#	Time	Username	Problem	Language	Result	Execution time	Memory
653219		beaconmc	Factories (JOI14_factories)	C++14	33 / 100	8096 ms	126300 KiB

factories

#pragma GCC optimize ("Ofast")

#include "factories.h"
#include <bits/stdc++.h>

#define ll long long
#define FOR(i,x,y) for(ll i=x; i<y; i++)

using namespace std;


bool r[600000];
vector<pair<ll,ll>> edges[600000];
ll sub[600000], par[600000], ans[600000];
ll n,m,root;

ll first[600000];
ll dists[600000];
vector<ll> euler;
vector<ll> updated;


void dfs2(ll a, ll p, ll v){
  first[a] = euler.size();
  euler.push_back(a);
  for (auto&i : edges[a]){
    if (i.first!=p){ 
      dfs2(i.first, a, v+i.second);
      euler.push_back(a);
    }
    
  }
  dists[a] = v;
}

int distmin(ll a, ll b){
  if (dists[a] < dists[b]){
    return a;
  }else{
    return b;
  }
}


int t[2*1048576];

void build() {
    for (int i=1048576-1;i>0;--i)
        t[i]=distmin(t[i<<1],t[i<<1|1]);
}

int query(int l,int r) {
    int minV=0;
    for (l+=1048576,r+=1048576;l<r;l>>=1,r>>=1) {

        if (l&1){
          minV=distmin(minV,t[l++]);

        }

        if (r&1){
          minV=distmin(minV,t[--r]);

        }
    }

    return minV;
}
 



ll dfs(ll a, ll p){

  sub[a] = 1;
  for (auto& i : edges[a]){
    if (i.first!=p && !r[i.first]) sub[a] += dfs(i.first, a);
  }
  return sub[a];
}

ll centroid(ll a, ll sz, ll p){

  for (auto&i : edges[a]){
    if (i.first!=p && !r[i.first] && sub[i.first]*2 > sz){
      return centroid(i.first, sz, a);
    }
  }
  return a;
}

void decomp(ll a, ll p){
  ll c = centroid(a, dfs(a, -1), -1);

  if (p!=-1){
    par[c] = p;
  }else{
    par[c] = -1;
  }




  r[c] = 1;
  for (auto&i : edges[c]){
    if (!r[i.first]) decomp(i.first, c);
  }
}

ll dist(ll a, ll b){
  if (first[a] > first[b]) swap(a,b);

  return dists[a] + dists[b] - 2*dists[query(first[a],first[b])];
}

void update(ll a){
  ll orig = a;
  ans[a] = 0;
  updated.push_back(a);
  ll distance = 0;

  while (par[a] != -1){
    distance = dist(orig, par[a]);

    a = par[a];
    
    ans[a] = min(ans[a], distance);
    updated.push_back(a);
  }
}

ll query(ll a){
  ll orig = a;
  ll distance = 0;
  ll tempans = 1000000000000000;

  tempans = min(tempans, ans[a]);


  while (par[a] != -1){
    distance = dist(orig, par[a]);
    a = par[a];
    tempans = min(tempans, distance + ans[a]);
  }
  return tempans;
}


void Init(int N, int A[], int B[], int D[]) {
  FOR(i,0,1048576) t[i] = 0;
  FOR(i,0,600000) sub[i] = 0, r[i] = 0, ans[i] = 1000000000000000;
  n = N;
  dists[0] = 1000000000000000;

  FOR(i,0,n-1){
    ll a,b,c;
    a = A[i]+1;
    b = B[i]+1;
    c = D[i];
    edges[a].push_back({b,c});
    edges[b].push_back({a,c});
  }
  dfs2(1,-1,0);

  FOR(i,0,euler.size()){
    t[i+1048576] =  euler[i];
  }
  build();



  decomp(1,-1);

}



long long Query(int S, int X[], int T, int Y[]) {
  updated.clear();
  ll anss = 1000000000000000;

  FOR(i,0,S){
    update(X[i]+1);
  }
  

  FOR(i,0,T){
    anss = min(anss, (ll) query(Y[i]+1));
  }
  for (auto&i : updated){
    ans[i] = 1000000000000000;
  }


  return anss;
}

Compilation message (stderr)

factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:8:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define FOR(i,x,y) for(ll i=x; i<y; i++)
......
  166 |   FOR(i,0,euler.size()){
      |       ~~~~~~~~~~~~~~~~           
factories.cpp:166:3: note: in expansion of macro 'FOR'
  166 |   FOR(i,0,euler.size()){
      |   ^~~

• Subtask 1: 15 / 15
• Subtask 2: 18 / 18
• Subtask 3: 0 / 67