oj.uz

Submission #40021

# Submission time Handle Problem Language Result Execution time Memory
40021 2018-01-25T11:02:23 Z funcsr Factories (JOI14_factories) C++14
100 / 100
 3277 ms 284308 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();
  //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 18 ms 222536 KB Output is correct
2 Correct 706 ms 222948 KB Output is correct
3 Correct 753 ms 222944 KB Output is correct
4 Correct 738 ms 222968 KB Output is correct
5 Correct 706 ms 223232 KB Output is correct
6 Correct 560 ms 223008 KB Output is correct
7 Correct 736 ms 222944 KB Output is correct
8 Correct 734 ms 223104 KB Output is correct
9 Correct 746 ms 223236 KB Output is correct
10 Correct 527 ms 223008 KB Output is correct
11 Correct 742 ms 222944 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 222536 KB Output is correct
2 Correct 1739 ms 249624 KB Output is correct
3 Correct 1846 ms 252600 KB Output is correct
4 Correct 1448 ms 251900 KB Output is correct
5 Correct 1790 ms 284308 KB Output is correct
6 Correct 1911 ms 252188 KB Output is correct
7 Correct 1254 ms 228984 KB Output is correct
8 Correct 1114 ms 229160 KB Output is correct
9 Correct 1172 ms 233564 KB Output is correct
10 Correct 1348 ms 228892 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 2689 ms 253940 KB Output is correct
2 Correct 2610 ms 252844 KB Output is correct
3 Correct 3149 ms 258780 KB Output is correct
4 Correct 3277 ms 258888 KB Output is correct
5 Correct 3042 ms 253224 KB Output is correct
6 Correct 2841 ms 281648 KB Output is correct
7 Correct 1880 ms 251900 KB Output is correct
8 Correct 2936 ms 252020 KB Output is correct
9 Correct 2889 ms 251368 KB Output is correct
10 Correct 2886 ms 251936 KB Output is correct
11 Correct 1294 ms 235872 KB Output is correct
12 Correct 1000 ms 230976 KB Output is correct
13 Correct 1154 ms 229084 KB Output is correct
14 Correct 1140 ms 228944 KB Output is correct
15 Correct 1347 ms 229700 KB Output is correct
16 Correct 1413 ms 229560 KB Output is correct