oj.uz

Submission #292394

# Submission time Handle Problem Language Result Execution time Memory
292394 2020-09-06T22:14:49 Z VROOM_VARUN Factories (JOI14_factories) C++14
33 / 100
 8000 ms 145900 KB 
/*
ID: varunra2
LANG: C++
TASK: factories
*/

#include <bits/stdc++.h>

#include "factories.h"
using namespace std;

#ifdef DEBUG
#include "lib/debug.h"
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define debug_arr(...) \
  cerr << "[" << #__VA_ARGS__ << "]:", debug_arr(__VA_ARGS__)
#pragma GCC diagnostic ignored "-Wsign-compare"
//#pragma GCC diagnostic ignored "-Wunused-parameter"
//#pragma GCC diagnostic ignored "-Wunused-variable"
#else
#define debug(...) 42
#endif

#define EPS 1e-9
#define IN(A, B, C) assert(B <= A && A <= C)
#define INF (int)1e9
#define MEM(a, b) memset(a, (b), sizeof(a))
#define MOD 1000000007
#define MP make_pair
#define PB push_back
#define all(cont) cont.begin(), cont.end()
#define rall(cont) cont.end(), cont.begin()
#define x first
#define y second

const double PI = acos(-1.0);
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> PII;
typedef map<int, int> MPII;
typedef multiset<int> MSETI;
typedef set<int> SETI;
typedef set<string> SETS;
typedef vector<int> VI;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef vector<string> VS;

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define trav(a, x) for (auto& a : x)
#define sz(x) (int)(x).size()
typedef pair<int, int> pii;
typedef vector<int> vi;
#pragma GCC diagnostic ignored "-Wsign-compare"
// util functions
#define MAXN (int)5e5 + 5
#define MAXSEG 20
int n;
int par[MAXN];
bool use[MAXN];
int sub[MAXN];
VII adj[MAXN];
int lca[MAXN][MAXSEG];
ll d[MAXN];
int tin[MAXN];
int tout[MAXN];
int timer = 0;

int dfs(int u, int v) {
  sub[u] = 1;
  for (auto& x : adj[u]) {
    if (x.x == v or use[x.x]) continue;
    sub[u] += dfs(x.x, u);
  }
  return sub[u];
}

int getCent(int u, int v, int siz) {
  for (auto& x : adj[u]) {
    if (x.x == v or use[x.x]) continue;
    if (sub[x.x] * 2 > siz) {
      return getCent(x.x, u, siz);
    }
  }
  return u;
}

void decompose(int u, int v, int cnt) {
  int cur = getCent(u, -1, dfs(u, -1));
  use[cur] = true;
  par[cur] = v;

  for (auto& x : adj[cur]) {
    if (use[x.x]) continue;
    decompose(x.x, cur, cnt);
  }
}

// inline void init_siz(int N) {
//   n = N;
//   adj.resize(n);
//   par.resize(n);
//   use.resize(n);
//   sub.resize(n);
//   lca.resize(n);
//   d.resize(n);
//   tin.resize(n);
//   tout.resize(n);
//   for (int i = 0; i < n; i++) {
//     lca[i].resize(20);
//     use[i] = false;
//   }
// }

void getAdj(int a[], int b[], int d[]) {
  debug(n);
  for (int i = 0; i < n - 1; i++) {
    int u, v, w;
    u = a[i];
    v = b[i];
    w = d[i];
    adj[u].PB(MP(v, w));
    adj[v].PB(MP(u, w));
  }
}

void dfsLCA(int u, int v) {
  tin[u] = ++timer;
  lca[u][0] = v;
  for (int i = 1; i < 20; i++) {
    int to = lca[u][i - 1];
    if (to == -1)
      lca[u][i] = -1;
    else
      lca[u][i] = lca[to][i - 1];
  }
  for (auto& x : adj[u]) {
    if (x.x == v) continue;
    d[x.x] = d[u] + x.y;
    dfsLCA(x.x, u);
  }
  tout[u] = ++timer;
}

bool isAnc(int u, int v) {
  if (u == -1) return true;
  if (v == -1) return false;
  return tin[u] <= tin[v] and tout[u] >= tout[v];
}

int getLCA(int u, int v) {
  if (isAnc(u, v)) return u;
  if (isAnc(v, u)) return v;
  for (int i = 19; i >= 0; i--) {
    if (!isAnc(lca[u][i], v)) {
      u = lca[u][i];
    }
  }
  return lca[u][0];
}

inline ll getDist(int u, int v) { return d[u] + d[v] - 2 * d[getLCA(u, v)]; }

ll mindist[MAXN];
bool vis[MAXN];

void Init(int N, int a[], int b[], int d[]) {
  // init_siz(N);
  n = N;
  getAdj(a, b, d);
  decompose(0, -1, 0);
  dfsLCA(0, -1);
  for (int i = 0; i < MAXN; i++) {
    mindist[i] = 0;
    vis[i] = false;
  }
}

// MPII mindist;

ll Query(int s, int x[], int t, int y[]) {
  // map<int, pair<ll, bool>> mindist;
  for (int i = 0; i < s; i++) {
    // okay so we need to traverse up from x[i];
    int u = x[i];
    while (u != -1) {
      if (vis[u]) {
        mindist[u] = min(mindist[u], getDist(u, x[i]));
      } else {
        vis[u] = true;
        mindist[u] = getDist(u, x[i]);
      }
      u = par[u];
    }
  }

  ll ret = (ll)1e17;

  for (int i = 0; i < t; i++) {
    int u = y[i];
    while (u != -1) {
      if (vis[u]) {
        ret = min(ret, mindist[u] + getDist(u, y[i]));
      }
      u = par[u];
    }
  }

  for (int i = 0; i < s; i++) {
    int u = x[i];
    while (u != -1) {
      vis[u] = false;
      u = par[u];
    }
  }
  for (int i = 0; i < t; i++) {
    int u = y[i];
    while (u != -1) {
      vis[u] = false;
      u = par[u];
    }
  }

  return ret;
}

// int main() {
// #ifndef ONLINE_JUDGE
//   freopen("factories.in", "r", stdin);
//   freopen("factories.out", "w", stdout);
// #endif
//   cin.sync_with_stdio(0);
//   cin.tie(0);

//   int N, q;
//   cin >> N >> q;

//   int a[N - 1];
//   int b[N - 1];
//   int d[N - 1];

//   for (int i = 0; i < N - 1; i++) {
//     cin >> a[i] >> b[i] >> d[i];
//   }

//   Init(N, a, b, d);

//   for (int i = 0; i < q; i++) {
//     int s, t;
//     cin >> s >> t;
//     int x[s];
//     int y[t];
//     for (int j = 0; j < s; j++) {
//       cin >> x[j];
//     }
//     for (int j = 0; j < t; j++) {
//       cin >> y[j];
//     }

//     cout << Query(s, x, t, y) << '\n';
//   }

//   return 0;
// }

Compilation message

factories.cpp: In function 'void getAdj(int*, int*, int*)':
factories.cpp:21:20: warning: statement has no effect [-Wunused-value]
   21 | #define debug(...) 42
      |                    ^~
factories.cpp:116:3: note: in expansion of macro 'debug'
  116 |   debug(n);
      |   ^~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 17024 KB Output is correct
2 Correct 585 ms 27896 KB Output is correct
3 Correct 1167 ms 28016 KB Output is correct
4 Correct 940 ms 27956 KB Output is correct
5 Correct 729 ms 28280 KB Output is correct
6 Correct 306 ms 27900 KB Output is correct
7 Correct 1149 ms 28080 KB Output is correct
8 Correct 1227 ms 27912 KB Output is correct
9 Correct 729 ms 28152 KB Output is correct
10 Correct 305 ms 27896 KB Output is correct
11 Correct 1137 ms 27688 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 16768 KB Output is correct
2 Correct 2355 ms 106752 KB Output is correct
3 Correct 7043 ms 108680 KB Output is correct
4 Correct 935 ms 122292 KB Output is correct
5 Correct 4145 ms 145900 KB Output is correct
6 Correct 7357 ms 128460 KB Output is correct
7 Correct 4364 ms 57080 KB Output is correct
8 Correct 514 ms 56972 KB Output is correct
9 Correct 1659 ms 60280 KB Output is correct
10 Correct 3794 ms 58368 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 17024 KB Output is correct
2 Correct 585 ms 27896 KB Output is correct
3 Correct 1167 ms 28016 KB Output is correct
4 Correct 940 ms 27956 KB Output is correct
5 Correct 729 ms 28280 KB Output is correct
6 Correct 306 ms 27900 KB Output is correct
7 Correct 1149 ms 28080 KB Output is correct
8 Correct 1227 ms 27912 KB Output is correct
9 Correct 729 ms 28152 KB Output is correct
10 Correct 305 ms 27896 KB Output is correct
11 Correct 1137 ms 27688 KB Output is correct
12 Correct 14 ms 16768 KB Output is correct
13 Correct 2355 ms 106752 KB Output is correct
14 Correct 7043 ms 108680 KB Output is correct
15 Correct 935 ms 122292 KB Output is correct
16 Correct 4145 ms 145900 KB Output is correct
17 Correct 7357 ms 128460 KB Output is correct
18 Correct 4364 ms 57080 KB Output is correct
19 Correct 514 ms 56972 KB Output is correct
20 Correct 1659 ms 60280 KB Output is correct
21 Correct 3794 ms 58368 KB Output is correct
22 Correct 3670 ms 132188 KB Output is correct
23 Correct 3499 ms 134852 KB Output is correct
24 Execution timed out 8054 ms 134700 KB Time limit exceeded
25 Halted 0 ms 0 KB -