oj.uz

Submission #40022

# Submission time Handle Problem Language Result Execution time Memory
40022 2018-01-25T11:03:50 Z funcsr Factories (JOI14_factories) C++14
100 / 100
 3397 ms 271244 KB 
#include "factories.h"
#include <iostream>
#include <queue>
#include <cassert>
#include <set>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
typedef pair<int, int> P;
typedef pair<long long, long long> P2;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(x) x.begin(), x.end()
#define uniq(x) x.erase(unique(all(x)), x.end())
#define index(x, y) (int)(lower_bound(all(x), y) - x.begin())
#define pb push_back
#define _1 first
#define _2 second
#define INF (1LL<<60)

int N;
vector<P> G[500000];
int R[500000];
long long W[500000];
int IN[500000], OUT[500000];
int rev[500000];
vector<int> T;

vector<int> T2;
int pos[500000];
int sparseL[20][1000000], sparseR[20][1000000];

void dfs(int x, int p, int r, long long w) {
  IN[x] = T.size();
  rev[IN[x]] = x;
  T.pb(x);

  pos[x] = T2.size();
  T2.pb(IN[x]);

  R[x] = r, W[x] = w;
  for (P pp : G[x]) if (pp._1 != p) {
    dfs(pp._1, x, r+1, w+pp._2);
    T2.pb(IN[x]);
  }
  OUT[x] = (int)T.size()-1;
}

inline int rmq_min(int l, int r) {
  int k = 31-__builtin_clz(r-l+1);
  return min(sparseL[k][l], sparseR[k][r]);
}
inline int lca(int x, int y) {
  if (x == y) return x;
  if (pos[x] > pos[y]) swap(x, y);
  return rev[rmq_min(pos[x], pos[y])];
}

void Init(int NN, int A[], int B[], int D[]) {
  N = NN;
  rep(i, N-1) {
    G[A[i]].pb(P(B[i], D[i]));
    G[B[i]].pb(P(A[i], D[i]));
  }
  dfs(0, -1, 0, 0);
  rep(i, T2.size()) sparseL[0][i] = sparseR[0][i] = T2[i];
  rep(k, 19) rep(i, T2.size()) {
    sparseL[k+1][i] = sparseL[k][i];
    sparseR[k+1][i] = sparseR[k][i];
    if (i+(1<<k) < T2.size()) sparseL[k+1][i] = min(sparseL[k+1][i], sparseL[k][i+(1<<k)]);
    if (i-(1<<k) >= 0) sparseR[k+1][i] = min(sparseR[k+1][i], sparseR[k][i-(1<<k)]);
  }
}

long long D[500000];
bool isS[500000], isT[500000];
vector<int> G2[500000];

long long ans;
P2 dfs(int x) {
  P2 m = P2(isS[x]?0:INF, isT[x]?0:INF);
  for (int t : G2[x]) {
    long long w = W[t]-W[x];
    P2 p = dfs(t);
    m._1 = min(m._1, p._1+w);
    m._2 = min(m._2, p._2+w);
  }
  ans = min(ans, m._1+m._2);
  return m;
}
long long Query(int S, int X[], int T, int Y[]) {
  vector<int> ps;
  rep(i, S) ps.pb(IN[X[i]]);
  rep(i, T) ps.pb(IN[Y[i]]);
  sort(all(ps)); uniq(ps);
  vector<int> new_ps(ps);
  rep(i, (int)ps.size()-1) {
    int v = lca(rev[ps[i]], rev[ps[i+1]]);
    if (v != rev[ps[i]] && v != rev[ps[i+1]]) new_ps.pb(IN[v]);
  }
  swap(new_ps, ps);
  sort(all(ps)); uniq(ps);
  stack<int> st;
  for (int &p : ps) p = rev[p];
  for (int v : ps) {
    D[v] = INF;
    while (!st.empty() && !(IN[st.top()] <= IN[v] && IN[v] <= OUT[st.top()])) st.pop();
    if (!st.empty()) {
      int p = st.top();
      G2[p].pb(v);
    }
    st.push(v);
  }

  rep(i, S) isS[X[i]] = true;
  rep(i, T) isT[Y[i]] = true;
  ans = INF;
  dfs(ps[0]);
  rep(i, S) isS[X[i]] = false;
  rep(i, T) isT[Y[i]] = false;
  for (int v : ps) G2[v].clear(), G2[v].shrink_to_fit();
  return ans;
}

Compilation message

factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:12:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, n) for (int i=0; i<(n); i++)
                                  ^
factories.cpp:66:3: note: in expansion of macro 'rep'
   rep(i, T2.size()) sparseL[0][i] = sparseR[0][i] = T2[i];
   ^
factories.cpp:12:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, n) for (int i=0; i<(n); i++)
                                  ^
factories.cpp:67:14: note: in expansion of macro 'rep'
   rep(k, 19) rep(i, T2.size()) {
              ^
factories.cpp:70:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (i+(1<<k) < T2.size()) sparseL[k+1][i] = min(sparseL[k+1][i], sparseL[k][i+(1<<k)]);
                  ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 222540 KB Output is correct
2 Correct 852 ms 222952 KB Output is correct
3 Correct 982 ms 222948 KB Output is correct
4 Correct 907 ms 222972 KB Output is correct
5 Correct 829 ms 223100 KB Output is correct
6 Correct 523 ms 223012 KB Output is correct
7 Correct 935 ms 222948 KB Output is correct
8 Correct 913 ms 222948 KB Output is correct
9 Correct 778 ms 223096 KB Output is correct
10 Correct 517 ms 223012 KB Output is correct
11 Correct 977 ms 222948 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 222540 KB Output is correct
2 Correct 2147 ms 249628 KB Output is correct
3 Correct 2021 ms 252604 KB Output is correct
4 Correct 1523 ms 251904 KB Output is correct
5 Correct 1715 ms 271244 KB Output is correct
6 Correct 2213 ms 252188 KB Output is correct
7 Correct 1679 ms 228984 KB Output is correct
8 Correct 1068 ms 229164 KB Output is correct
9 Correct 1216 ms 230804 KB Output is correct
10 Correct 1652 ms 228892 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 2827 ms 250164 KB Output is correct
2 Correct 2814 ms 250296 KB Output is correct
3 Correct 3284 ms 252624 KB Output is correct
4 Correct 3397 ms 253356 KB Output is correct
5 Correct 3322 ms 251648 KB Output is correct
6 Correct 2686 ms 269088 KB Output is correct
7 Correct 1929 ms 251904 KB Output is correct
8 Correct 3247 ms 251692 KB Output is correct
9 Correct 3176 ms 251180 KB Output is correct
10 Correct 3114 ms 251012 KB Output is correct
11 Correct 1336 ms 234820 KB Output is correct
12 Correct 1061 ms 230792 KB Output is correct
13 Correct 1470 ms 228408 KB Output is correct
14 Correct 1539 ms 228540 KB Output is correct
15 Correct 2092 ms 228900 KB Output is correct
16 Correct 1797 ms 228892 KB Output is correct