Submission #1231383

#TimeUsernameProblemLanguageResultExecution timeMemory
1231383KhoaDuyFactories (JOI14_factories)C++20
Compilation error
0 ms0 KiB
#define taskname "01-01"
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int kN = 500005;
const int kLG = 20;
const long long kInf = 91632847297843575;

vector<pair<int, int>> children[kN];
int in[kN], out[kN], jump[kLG][kN], timer, w[kN];
bool markX[kN], markY[kN];
long long p[kN], dp[2][kN];
vector<pair<int, long long>> vt[kN];

void DFS(int u, int v) {
  in[u] = ++timer;
  jump[0][u] = v;
  for (int i = 1; i < kLG; i++) {
    jump[i][u] = jump[i - 1][jump[i - 1][u]];
  }
  for (auto i : children[u]) {
   if (i.first == v) {
     continue;
   }
   p[i.first]=p[u]+i.second;
   DFS(i.first, u);
   w[i.first] = i.second;
  }
  out[u] = timer;
}

bool Ancestor(int u, int v) {
  return (in[v] <= in[u] && out[u] <= out[v]);
}

int LCA(int u, int v) {
  if (Ancestor(u, v)) {
   return v;
  }
  for (int i = kLG - 1; i >= 0; i--) {
   if (jump[i][v] != -1 && !Ancestor(u, jump[i][v])) {
     v = jump[i][v];
   }
  }
  return jump[0][v];
}

bool DFSTimer(int u, int v) {
  return in[u] < in[v];
}

long long SumPath(int x, int y) {
  return p[y] + p[x] - 2 * p[LCA(x, y)];
}

void Init(int N, int A[], int B[], int D[]) {
  memset(jump, -1, sizeof(jump));
  for (int i = 0; i < N - 1; i++) {
   children[A[i]].push_back(make_pair(B[i], D[i]));
   children[B[i]].push_back(make_pair(A[i], D[i]));
  }
  int root = 0;
  DFS(root, root);
  for (int i = 0; i < N; i++) {
   for (int j = 0; j < 2; j++) {
     dp[j][i] = kInf;
   }
  }
}

long long Query(int S, int X[], int T, int Y[]) {
  vector<int> u;
  for (int i = 0; i < S; i++) {
   markX[X[i]] = true;
   u.push_back(X[i]);
  }
  for (int i = 0; i < T; i++) {
   markY[Y[i]] = true;
   u.push_back(Y[i]);
  }

  sort(u.begin(), u.end(), DFSTimer);
  int l = u.size() - 1;
  for (int i = 0; i < l; i++) {
   u.push_back(LCA(u[i], u[i + 1]));
  }
  sort(u.begin(), u.end(), DFSTimer);
  u.erase(unique(u.begin(), u.end()), u.end());
  stack<int> st;
  st.push(u[0]);
  for (int i = 1; i < u.size(); i++) {
    while (!st.empty() && !Ancestor(u[i], st.top())) {
      st.pop();
    }
    vt[st.top()].push_back(make_pair(u[i], SumPath(st.top(), u[i])));
    st.push(u[i]);
  }

  function<void(int i)> CalculateDP = [&](int i) {
   if (markX[i]) {
     dp[0][i] = 0;
   }
   if (markY[i]) {
     dp[1][i] = 0;
   }
   for (auto j : vt[i]) {
     CalculateDP(j.first);
     if (dp[0][j.first] != kInf) {
       dp[0][i] = min(dp[0][i], dp[0][j.first] + j.second);
     }
     if (dp[1][j.first] != kInf) {
       dp[1][i] = min(dp[1][i], dp[1][j.first] + j.second);
     }
   }
  };

  CalculateDP(u[0]);

  long long result = kInf;
  for (int i : u) {
   if (dp[0][i] != kInf && dp[1][i] != kInf) {
     result = min(result, dp[0][i] + dp[1][i]);
   }
  }

  for (int i : u) {
   dp[0][i] = dp[1][i] = kInf;
   vt[i].clear();
  }
  for (int i = 0; i < S; i++) {
   markX[X[i]] = false;
  }
  for (int i = 0; i < T; i++) {
   markY[Y[i]] = false;
  }

  return result;
}

int32_t main() {
   if (fopen(taskname".txt", "r")) {
     freopen(taskname".txt", "r", stdin);
     freopen(taskname".out", "w", stdout);
   }
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);

  int N, Q;
  cin >> N >> Q;
  int A[N], B[N], D[N];

  for (int i = 0; i < N - 1; i++) {
    cin >> A[i] >> B[i] >> D[i];
  }
 Init(N, A, B, D);

 while (Q--) {
   int S, T;
   cin >> S >> T;
   int X[S], Y[T];
   for (int i = 0; i < S; i++) {
     cin >> X[i];
   }
   for (int j = 0; j < T; j++) {
     cin >> Y[j];
   }
   cout << Query(S, X, T, Y) << '\n';
 }

  return 0;
}

Compilation message (stderr)

factories.cpp: In function 'int32_t main()':
factories.cpp:142:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |      freopen(taskname".txt", "r", stdin);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
factories.cpp:143:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  143 |      freopen(taskname".out", "w", stdout);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccGmsqvj.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccEIPDan.o:factories.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccGmsqvj.o: in function `main':
grader.cpp:(.text.startup+0x3d5): undefined reference to `Init(int, int*, int*, int*)'
/usr/bin/ld: grader.cpp:(.text.startup+0x468): undefined reference to `Query(int, int*, int, int*)'
collect2: error: ld returned 1 exit status