Submission #887406

#	Time	Username	Problem	Language	Result	Execution time	Memory
887406		Zero_OP	Factories (JOI14_factories)	C++14	100 / 100	3727 ms	191756 KiB

factories

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

using namespace std;

#define range(v) begin(v), end(v)
#define compact(v) v.erase(unique(range(v)), end(v))

template<class T> bool minimize(T& a, T b){
  if(a > b) return a = b, true;
  return false;
}

template<class T> bool maximize(T& a, T b){
  if(a < b) return a = b, true;
  return false;
}

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const int N = 5e5 + 5;
const ll inf = 1e18;

int n, q, h[N], pos[N], rmq[20][N + N], par[N], timerDFS, sz[N];
ll depth[N], dp[N];
bool del[N];
vector<pair<int, int>> g[N];

void dfs(int u, int e){
  rmq[0][pos[u] = timerDFS++] = u;
  for(auto [v, w] : g[u]) if(v != e){
    h[v] = h[u] + 1;
    depth[v] = depth[u] + w;
    dfs(v, u);
    rmq[0][timerDFS++] = u;
  }
}

int combine(int u, int v){
  return h[u] < h[v] ? u : v;
}

void prepareRMQ(){
  for(int i = 1; (1 << i) <= timerDFS; ++i){
    for(int j = 0; j + (1 << i) <= timerDFS; ++j){
      rmq[i][j] = combine(rmq[i - 1][j], rmq[i - 1][j + (1 << (i - 1))]);
    }
  }
}

int getLCA(int u, int v){
  u = pos[u], v = pos[v];
  if(u > v) swap(u, v);
  int b = __lg(v - u + 1);
  return combine(rmq[b][u], rmq[b][v - (1 << b) + 1]);
}

ll getDist(int u, int v){
  return depth[u] + depth[v] - 2 * depth[getLCA(u, v)];
}

int dfsSize(int u, int e){
  sz[u] = 1;
  for(auto [v, w] : g[u]) if(v != e and !del[v]){
    sz[u] += dfsSize(v, u);
  }
  return sz[u];
}

int getCentroid(int u, int e, int target){
  for(auto [v, w] : g[u]) if(v != e and !del[v] and sz[v] * 2 > target){
    return getCentroid(v, u, target);
  }
  return u;
}

void decompose(int u, int e){
  int c = getCentroid(u, e, dfsSize(u, e));
  par[c] = e;
  del[c] = true;
  for(auto [v, w] : g[c]) if(!del[v]){
    decompose(v, c);
  }
}

void update(int u){
  dp[u] = 0;
  int nxt = u;
  while(par[nxt] != -1){
    nxt = par[nxt];
    minimize(dp[nxt], getDist(nxt, u));
  }
}

ll query(int u){
  ll ans = dp[u];
  int nxt = u;
  while(par[nxt] != -1){
    nxt = par[nxt];
    minimize(ans, dp[nxt] + getDist(nxt, u));
  }
  return ans;
}

void resetData(int u){
  dp[u] = inf;
  while(par[u] != -1){
    u = par[u];
    dp[u] = inf;
  }
}

void Init(int N, int A[], int B[], int D[]){
  n = N;
  for(int i = 0; i + 1 < n; ++i){
    g[A[i]].push_back({B[i], D[i]});
    g[B[i]].push_back({A[i], D[i]});
  }

  fill(dp, dp + n, inf);
  dfs(0, -1);
  decompose(0, -1);
  prepareRMQ();
}

long long Query(int S, int X[], int T, int Y[]){
  ll ans = inf;
  for(int i = 0; i < S; ++i){
    update(X[i]);
  }

  for(int i = 0; i < T; ++i){
    minimize(ans, query(Y[i]));
  }

  for(int i = 0; i < S; ++i){
    resetData(X[i]);
  }

  return ans;
}

Compilation message (stderr)

factories.cpp: In function 'void dfs(int, int)':
factories.cpp:33:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   33 |   for(auto [v, w] : g[u]) if(v != e){
      |            ^
factories.cpp: In function 'int dfsSize(int, int)':
factories.cpp:66:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   66 |   for(auto [v, w] : g[u]) if(v != e and !del[v]){
      |            ^
factories.cpp: In function 'int getCentroid(int, int, int)':
factories.cpp:73:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   73 |   for(auto [v, w] : g[u]) if(v != e and !del[v] and sz[v] * 2 > target){
      |            ^
factories.cpp: In function 'void decompose(int, int)':
factories.cpp:83:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   83 |   for(auto [v, w] : g[c]) if(!del[v]){
      |            ^

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