oj.uz

답안 #319695

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
319695 2020-11-06T07:23:50 Z tushar_2658 공장들 (JOI14_factories) C++14
15 / 100
 8000 ms 234552 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];

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){
  dfs(x, p);
  int c = find_centroid(x, 0, sub[x] / 2);
  par[c] = p;
  vector<int> v;
  copy(G[c].begin(), G[c].end(), back_inserter(v));
  for(auto i : v){
    rem(c, i);
    build(i, c);
  }
}

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

void upd(int x, bool keep){
  int cur = x;
  while(cur != 0){
    if(keep){
      mn[cur] = min(mn[cur], DIS(cur, x));
    }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] + DIS(x, 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);
  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 89 ms 114404 KB Output is correct
2 Correct 1305 ms 132512 KB Output is correct
3 Correct 2313 ms 132500 KB Output is correct
4 Correct 2252 ms 132460 KB Output is correct
5 Correct 2669 ms 132984 KB Output is correct
6 Correct 552 ms 132452 KB Output is correct
7 Correct 2252 ms 132708 KB Output is correct
8 Correct 2378 ms 132548 KB Output is correct
9 Correct 2710 ms 132876 KB Output is correct
10 Correct 532 ms 132456 KB Output is correct
11 Correct 2268 ms 132632 KB Output is correct

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 66 ms 114020 KB Output is correct
2 Correct 4528 ms 231736 KB Output is correct
3 Execution timed out 8092 ms 234552 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 89 ms 114404 KB Output is correct
2 Correct 1305 ms 132512 KB Output is correct
3 Correct 2313 ms 132500 KB Output is correct
4 Correct 2252 ms 132460 KB Output is correct
5 Correct 2669 ms 132984 KB Output is correct
6 Correct 552 ms 132452 KB Output is correct
7 Correct 2252 ms 132708 KB Output is correct
8 Correct 2378 ms 132548 KB Output is correct
9 Correct 2710 ms 132876 KB Output is correct
10 Correct 532 ms 132456 KB Output is correct
11 Correct 2268 ms 132632 KB Output is correct
12 Correct 66 ms 114020 KB Output is correct
13 Correct 4528 ms 231736 KB Output is correct
14 Execution timed out 8092 ms 234552 KB Time limit exceeded
15 Halted 0 ms 0 KB -