oj.uz

답안 #319699

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
319699 2020-11-06T08:07:43 Z tushar_2658 공장들 (JOI14_factories) C++14
15 / 100
 8000 ms 333912 KB 
#include "factories.h"
#include "bits/stdc++.h"
using namespace std;

const int maxn = 500005;
using ll = long long;

vector<pair<int, ll>> edges[maxn];
int n;
ll dis[maxn], sparse[maxn][20];
int depth[maxn];

void dfs(int x, int p, ll c){
  dis[x] = c;
  depth[x] = depth[p] + 1;
  sparse[x][0] = p;
  for(auto i : edges[x]){
    if(i.first != p){
      dfs(i.first, x, c + i.second);
    }
  }
} 

void build_lca(){
  for(int j = 1; j < 20; ++j){
    for(int i = 1; i <= n; ++i){
      if(sparse[i][j - 1] != -1){
        sparse[i][j] = sparse[sparse[i][j - 1]][j - 1];
      }
    }
  }
}

int LCA(int x, int y){
  if(depth[x] < depth[y])swap(x, y);
  for(int i = 19; i >= 0; --i){
    if(depth[x] - (1 << i) >= depth[y]){
      x = sparse[x][i];
    }
  }
  if(x == y)return x;
  for(int i = 19; i >= 0; --i){
    if(sparse[x][i] != sparse[y][i] && sparse[x][i] != -1 && sparse[y][i] != -1){
      x = sparse[x][i];
      y = sparse[y][i];
    }
  }
  return sparse[x][0];
}

ll DIS(int x, int y){
  return dis[x] + dis[y] - (2 * dis[LCA(x, y)]);
}

set<int> G[maxn];
int sub[maxn], par[maxn], cent_dep[maxn];

void rem(int x, int y){
  G[x].erase(y);
  G[y].erase(x);
}

void dfs(int x, int p){
  sub[x] = 1;
  for(auto i : G[x]){
    if(i != p){
      dfs(i, x);
      sub[x] += sub[i];
    }
  }
}

int find_centroid(int x, int p, int range){
  for(auto i : G[x]){
    if(i != p){
      if(sub[i] > range)return find_centroid(i, x, range);
    }
  }return x;
}

void build(int x, int p, int d){
  dfs(x, p);
  int c = find_centroid(x, 0, sub[x] / 2);
  par[c] = p;
  cent_dep[c] = d;
  vector<int> v;
  copy(G[c].begin(), G[c].end(), back_inserter(v));
  for(auto i : v){
    rem(c, i);
    build(i, c, d + 1);
  }
}

vector<int> vis(n + 1);
ll mn[maxn], cent_dis[maxn][20];

void calc(int x){
  int cur = x, lvl = 0;
  while(cur != 0){
    cent_dis[x][lvl] = DIS(cur, x);
    cur = par[cur];
    ++lvl;
  }
}

void upd(int x, bool keep){
  int cur = x;
  while(cur != 0){
    if(keep){
      mn[cur] = min(mn[cur], cent_dis[x][cent_dep[x] - cent_dep[cur]]);
    }else {
      mn[cur] = 1e18;
    }
    cur = par[cur];
  }
}

ll query(int x){
  ll ret = mn[x];
  int cur = x;
  while(cur != 0){
    ret = min(ret, mn[cur] + cent_dis[x][cent_dep[x] - cent_dep[cur]]);
    cur = par[cur];
  }
  return ret;
}

void Init(int N, int A[], int B[], int D[]) {
  n = N;
  for(int i = 0; i < N - 1; ++i){
    edges[A[i] + 1].push_back({B[i] + 1, D[i]});
    edges[B[i] + 1].push_back({A[i] + 1, D[i]});
    G[A[i] + 1].insert(B[i] + 1);
    G[B[i] + 1].insert(A[i] + 1);
  }
  memset(sparse, -1, sizeof sparse);
  dfs(1, 1, 0);
  build_lca();
  build(1, 0, 1);
  for(int i = 1; i <= N; ++i){
    calc(i);
  }
//  cout << cent_dis[7][2] << endl;
  for(int i = 0; i <= N; ++i){
    mn[i] = 1e18;
  }
}

long long Query(int S, int X[], int T, int Y[]) {
  for(int i = 0; i < S; ++i){
    upd(X[i] + 1, 1);
  }
  ll ans = 1e18;
  for(int i = 0; i < T; ++i){
    ans = min(ans, query(Y[i] + 1));
  }
  for(int i = 0; i < S; ++i){
    upd(X[i] + 1, 0);
  }
  return ans;
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 65 ms 114404 KB Output is correct
2 Correct 409 ms 123616 KB Output is correct
3 Correct 445 ms 123676 KB Output is correct
4 Correct 441 ms 123748 KB Output is correct
5 Correct 469 ms 124004 KB Output is correct
6 Correct 322 ms 123620 KB Output is correct
7 Correct 439 ms 123768 KB Output is correct
8 Correct 443 ms 123620 KB Output is correct
9 Correct 466 ms 124004 KB Output is correct
10 Correct 325 ms 123748 KB Output is correct
11 Correct 452 ms 123620 KB Output is correct

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 114148 KB Output is correct
2 Correct 3645 ms 293396 KB Output is correct
3 Correct 7199 ms 297332 KB Output is correct
4 Correct 2045 ms 313392 KB Output is correct
5 Execution timed out 8090 ms 333912 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 65 ms 114404 KB Output is correct
2 Correct 409 ms 123616 KB Output is correct
3 Correct 445 ms 123676 KB Output is correct
4 Correct 441 ms 123748 KB Output is correct
5 Correct 469 ms 124004 KB Output is correct
6 Correct 322 ms 123620 KB Output is correct
7 Correct 439 ms 123768 KB Output is correct
8 Correct 443 ms 123620 KB Output is correct
9 Correct 466 ms 124004 KB Output is correct
10 Correct 325 ms 123748 KB Output is correct
11 Correct 452 ms 123620 KB Output is correct
12 Correct 59 ms 114148 KB Output is correct
13 Correct 3645 ms 293396 KB Output is correct
14 Correct 7199 ms 297332 KB Output is correct
15 Correct 2045 ms 313392 KB Output is correct
16 Execution timed out 8090 ms 333912 KB Time limit exceeded
17 Halted 0 ms 0 KB -