Submission #1269189

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269189		repmann	Factories (JOI14_factories)	C++20	0 / 100	8076 ms	589824 KiB

factories

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int N;
bool V[500001];
int SIZE[500001];
vector <pair <int, int>> VG[500001];
vector <pair <ll, int>> UP[500001];
ll DP[500001];
inline int SDFS(int node, int parent = -1)
{
  SIZE[node] = 1;
  for(pair <int, int> p : VG[node]) if(!V[p.second] && (p.second != parent)) SIZE[node] += SDFS(p.second, node);
  return SIZE[node];
}
inline int CDFS(int node, int num, int parent = -1)
{
  int temp = 0;
  for(pair <int, int> p : VG[node]) if((!V[p.second] && (p.second != parent)) && (SIZE[p.second] > SIZE[temp])) temp = p.second;
  if(SIZE[temp] <= num) return temp;
  return CDFS(temp, num, node);
}
inline void DFS(int node, int root, ll depth, int parent = -1)
{
  UP[node].push_back({depth, root});
  for(pair <int, int> p : VG[node]) if(!V[p.second] && (p.second != parent)) DFS(p.second, root, depth + p.first, node);
  return;
}
inline void CD(int root = 1)
{
  SDFS(root);
  int centroid = CDFS(root, (SIZE[root] + 1) >> 1);
  DFS(centroid, centroid, 0);
  V[centroid] = 1;
  for(pair <int, int> p : VG[centroid]) if(!V[p.second]) CD(p.second);
  return;
}
void Init(int n, int u[], int v[], int w[])
{
  N = n;
  for(int i = 0; i < (N - 1); i++)
  {
    VG[u[i] + 1].push_back({w[i], v[i] + 1});
    VG[v[i] + 1].push_back({w[i], u[i] + 1});
  }
  CD();
  for(int i = 1; i <= N; i++) DP[i] = 1e18;
  return;
}
ll Query(int n, int X[], int m, int Y[])
{
  ll ret = 1e18;
  for(int i = 0; i < n; i++) for(pair <ll, int> p : UP[X[i] + 1]) DP[p.second] = min(p.first, DP[p.second]);
  for(int i = 0; i < m; i++) for(pair <ll, int> p : UP[Y[i] + 1]) ret = min(p.first + DP[p.second], ret);
  for(int i = 0; i < n; i++) for(pair <ll, int> p : UP[X[i] + 1]) DP[p.second] = 1e18;
  return ret;
}
//int main()
//{
//  int n, m;
//  cin >> n;
//  int u[n], v[n], w[n];
//  for(int i = 0; i < (n - 1); i++) cin >> u[i] >> v[i] >> w[i];
//  Init(n, u, v, w);
//  while(true)
//  {
//    cin >> n >> m;
//    int x[n], y[m];
//    for(int i = 0; i < n; i++) cin >> x[i];
//    for(int i = 0; i < m; i++) cin >> y[i];
//    cout << "ans: " << Query(n, x, m, y) << '\n';
//  }
//
//  return 0;
//}

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