Submission #1269192

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269192		repmann	공장들 (JOI14_factories)	C++20	15 / 100	8112 ms	571892 KiB

factories

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int N;
bool V[500001];
int SIZE[500001];
queue <pair <int, int>> Q;
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;
  Q.push({node, parent});
  for(pair <int, int> p : VG[node]) if(!V[p.second] && (p.second != parent)) SIZE[node] += SDFS(p.second, node);
  return SIZE[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 = root, best = INT_MAX, temp;
  while(Q.size())
  {
    temp = 0;
    for(pair <int, int> p : VG[Q.front().first])
    {
      if(V[p.second]) continue;
      if(p.second != Q.front().second) temp = max(SIZE[p.second], temp);
      else temp = max(SIZE[root] - SIZE[p.second] + 1, temp);
    }
    if(temp < best) {centroid = Q.front().first; best = temp;}
    Q.pop();
  }
  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: 15 / 15
• Subtask 2: 0 / 18
• Subtask 3: 0 / 67