oj.uz

Submission #29231

# Submission time Handle Problem Language Result Execution time Memory
29231 2017-07-18T19:00:09 Z ruhanhabib39 Factories (JOI14_factories) C++14
100 / 100
 4976 ms 212464 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5e5;
const int MAXLG = 20;
const long long INF = 1e18;

int N;
vector<pair<int,int>> G[MAXN + 10];

int cc[MAXN + 10];
int level[MAXN + 10];
long long dis[MAXN + 10][MAXLG + 10];
bool done[MAXN + 10];
int par[MAXN + 10];

void dfs(int u, int p, long long ds) {
   dis[u][++level[u]] = ds;
   cc[u] = 1;
   for(auto e : G[u]) {
      int v, d; tie(v, d) = e;
      if(v == p || done[v]) continue;
      dfs(v, u, ds + d);
      cc[u] += cc[v];
   }
}

int centroid(int u, int p, int cnt) {
   for(auto e : G[u]) {
      int v = e.first;
      if(v == p || done[v]) continue;
      if(cc[v] > cnt/2) return centroid(v, u, cnt);
   }
   return u;
}

void decomp(int u, int p) {
   u = centroid(u, -1, cc[u]); dfs(u, -1, 0);
   // cerr << "centroid = " << u << "\n";
   par[u] = p;
   done[u] = true;
   for(auto e : G[u]) {
      int v = e.first;
      if(done[v]) continue;
      decomp(v, u);
   }
}

long long mn[MAXN + 10];

void Init(int N_, int A[], int B[], int D[]) {
   N = N_;
   for(int i = 0; i < N-1; i++) {
      G[A[i]].emplace_back(B[i], D[i]);
      G[B[i]].emplace_back(A[i], D[i]);
   }
   memset(level, -1, sizeof(level));
   dfs(0, -1, 0);
   decomp(0, -1);
   std::fill(mn, mn + MAXN + 1, INF);
}

long long Query(int S, int X[], int T, int Y[]) {
   // cerr << "\n\n";
   for(int i = 0; i < S; i++) {
      int u = X[i];
      // cerr << "Xu = " << u << "\n";
      for(int j = level[u]; j > 0; j--) {
         mn[u] = min(mn[u], dis[X[i]][j]);
         // cerr << "mn[" << u << "] = " << mn[u] << "\n";
         u = par[u];
      }
   }
   long long res = INF;
   for(int i = 0; i < T; i++) {
      int u = Y[i];
      for(int j = level[u]; j > 0; j--) {
         res = min(res, mn[u] + dis[Y[i]][j]);
         u = par[u];
      }
   }
   for(int i = 0; i < S; i++) {
      int u = X[i];
      for(int j = level[u]; j > 0; j--) {
         mn[u] = INF;
         u = par[u];
      }
   }
   return res;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 163452 KB Output is correct
2 Correct 373 ms 163716 KB Output is correct
3 Correct 363 ms 163716 KB Output is correct
4 Correct 373 ms 163716 KB Output is correct
5 Correct 419 ms 163808 KB Output is correct
6 Correct 299 ms 163752 KB Output is correct
7 Correct 366 ms 163716 KB Output is correct
8 Correct 353 ms 163716 KB Output is correct
9 Correct 353 ms 163808 KB Output is correct
10 Correct 273 ms 163752 KB Output is correct
11 Correct 329 ms 163716 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 163452 KB Output is correct
2 Correct 2609 ms 182196 KB Output is correct
3 Correct 3319 ms 186096 KB Output is correct
4 Correct 1243 ms 183164 KB Output is correct
5 Correct 4499 ms 212464 KB Output is correct
6 Correct 3866 ms 185556 KB Output is correct
7 Correct 1029 ms 167860 KB Output is correct
8 Correct 539 ms 167684 KB Output is correct
9 Correct 1273 ms 170560 KB Output is correct
10 Correct 946 ms 167744 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 3096 ms 182196 KB Output is correct
2 Correct 2473 ms 182196 KB Output is correct
3 Correct 3999 ms 184860 KB Output is correct
4 Correct 4219 ms 185576 KB Output is correct
5 Correct 4486 ms 185412 KB Output is correct
6 Correct 4336 ms 205240 KB Output is correct
7 Correct 1449 ms 183164 KB Output is correct
8 Correct 4673 ms 184952 KB Output is correct
9 Correct 4976 ms 184288 KB Output is correct
10 Correct 3429 ms 185004 KB Output is correct
11 Correct 1022 ms 171160 KB Output is correct
12 Correct 573 ms 167684 KB Output is correct
13 Correct 656 ms 167148 KB Output is correct
14 Correct 873 ms 167148 KB Output is correct
15 Correct 1073 ms 167748 KB Output is correct
16 Correct 1006 ms 167732 KB Output is correct