oj.uz

Submission #1048040

# Submission time Handle Problem Language Result Execution time Memory
1048040 2024-08-07T20:32:35 Z beaconmc Factories (JOI14_factories) C++14
100 / 100
 6759 ms 312888 KB 
#include "factories.h"

#include <bits/stdc++.h>
 
typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
 
using namespace std;
const ll INF = 1000000000000000;
vector<vector<ll>> edges[500005];
ll ancc[500005][30];
ll par[500005];
ll depth[500005];
ll realdepth[500005];
ll tin[500005];
ll timer = 0;
ll anc(ll a, ll x){
  if (a==0) return 0;
  if (x==0) return par[a];
  if (ancc[a][x] != -1) return ancc[a][x];
  return ancc[a][x] = anc(anc(a, x-1), x-1);
}

ll lca(ll a, ll b){
  if (depth[a] < depth[b]) swap(a,b);

  FORNEG(i,19,-1) if (depth[anc(a,i)] >= depth[b]) a = anc(a,i);
  if (a==b) return a;
  FORNEG(i,19,-1) if (anc(a,i) != anc(b,i)) a = anc(a,i), b = anc(b,i);
  return par[a];
}

void dfs(ll a, ll p, ll d, ll dd){
  tin[a] = timer++;
  par[a] = p;
  depth[a] = d;
  realdepth[a] = dd;

  for (auto&i : edges[a]){
    if (i[0] != p) dfs(i[0], a, d+1, dd+i[1]);
  }
}
void Init(int N, int A[], int B[], int D[]) {
  FOR(i,0,500005) edges[i].clear(), par[i] = -1, depth[i] = 0, realdepth[i] = -1;
  FOR(i,0,500005) FOR(j,0,30) ancc[i][j] = -1;

  FOR(i,0,N){
    edges[A[i]].push_back({B[i], D[i]});
    edges[B[i]].push_back({A[i], D[i]});
  }
  dfs(0, -1, 0,0);

}
ll mina[500005];
ll minb[500005];
vector<vector<ll>> vtree[500005];
void dp(ll a){
  for (auto&i : vtree[a]){
    dp(i[0]);
    mina[a] = min(mina[a], mina[i[0]] + i[1]);
    minb[a] = min(minb[a], minb[i[0]] + i[1]);
  }

}

long long Query(int S, int X[], int T, int Y[]) {
  vector<vector<ll>> stuff;
  FOR(i,0,S) stuff.push_back({tin[X[i]],X[i]});
  FOR(i,0,T) stuff.push_back({tin[Y[i]], Y[i]});

  sort(stuff.begin(), stuff.end());
  set<vector<ll>> stuff2;


  FOR(i,1,stuff.size()){
    stuff2.insert({tin[lca(stuff[i][1], stuff[i-1][1])], lca(stuff[i][1], stuff[i-1][1])});
  }
  if (stuff.size()){
    ll temp = lca(stuff[0][1], stuff[stuff.size()-1][1]);
    stuff2.insert({tin[temp], temp});
  }

  for (auto&i : stuff) stuff2.insert(i);

  vector<ll> stack;
  for (auto&i : stuff2) mina[i[1]] = INF, minb[i[1]] = INF, vtree[i[1]].clear();

  FOR(i,0,S) mina[X[i]] = 0;
  FOR(i,0,T) minb[Y[i]] = 0;
  for (auto&i : stuff2){
    while (stack.size() && lca(stack[stack.size()-1], i[1])!= stack[stack.size()-1])stack.pop_back();
    if (stack.size()) vtree[stack[stack.size()-1]].push_back({i[1], realdepth[i[1]] - realdepth[stack[stack.size()-1]]});
    stack.push_back(i[1]);
  }

  dp((*stuff2.begin())[1]);


  ll ans = INF;
  for (auto&i : stuff2) ans = min(ans, mina[i[1]] + minb[i[1]]);
  



  return ans;
}

Compilation message

factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:6:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define FOR(i,x,y) for(ll i=x; i<y; i++)
......
   76 |   FOR(i,1,stuff.size()){
      |       ~~~~~~~~~~~~~~~~           
factories.cpp:76:3: note: in expansion of macro 'FOR'
   76 |   FOR(i,1,stuff.size()){
      |   ^~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 168792 KB Output is correct
2 Correct 1932 ms 174560 KB Output is correct
3 Correct 2351 ms 173912 KB Output is correct
4 Correct 2062 ms 174904 KB Output is correct
5 Correct 1488 ms 175016 KB Output is correct
6 Correct 1393 ms 174360 KB Output is correct
7 Correct 2323 ms 174060 KB Output is correct
8 Correct 2028 ms 174884 KB Output is correct
9 Correct 1463 ms 174808 KB Output is correct
10 Correct 1348 ms 174352 KB Output is correct
11 Correct 2293 ms 173908 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 168796 KB Output is correct
2 Correct 2090 ms 250248 KB Output is correct
3 Correct 3247 ms 258492 KB Output is correct
4 Correct 1143 ms 244512 KB Output is correct
5 Correct 3616 ms 300120 KB Output is correct
6 Correct 3478 ms 258508 KB Output is correct
7 Correct 3368 ms 190212 KB Output is correct
8 Correct 1348 ms 187388 KB Output is correct
9 Correct 2341 ms 197796 KB Output is correct
10 Correct 3267 ms 190544 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 168792 KB Output is correct
2 Correct 1932 ms 174560 KB Output is correct
3 Correct 2351 ms 173912 KB Output is correct
4 Correct 2062 ms 174904 KB Output is correct
5 Correct 1488 ms 175016 KB Output is correct
6 Correct 1393 ms 174360 KB Output is correct
7 Correct 2323 ms 174060 KB Output is correct
8 Correct 2028 ms 174884 KB Output is correct
9 Correct 1463 ms 174808 KB Output is correct
10 Correct 1348 ms 174352 KB Output is correct
11 Correct 2293 ms 173908 KB Output is correct
12 Correct 29 ms 168796 KB Output is correct
13 Correct 2090 ms 250248 KB Output is correct
14 Correct 3247 ms 258492 KB Output is correct
15 Correct 1143 ms 244512 KB Output is correct
16 Correct 3616 ms 300120 KB Output is correct
17 Correct 3478 ms 258508 KB Output is correct
18 Correct 3368 ms 190212 KB Output is correct
19 Correct 1348 ms 187388 KB Output is correct
20 Correct 2341 ms 197796 KB Output is correct
21 Correct 3267 ms 190544 KB Output is correct
22 Correct 4991 ms 280200 KB Output is correct
23 Correct 4595 ms 280876 KB Output is correct
24 Correct 6254 ms 291836 KB Output is correct
25 Correct 6033 ms 292204 KB Output is correct
26 Correct 6545 ms 262176 KB Output is correct
27 Correct 5296 ms 312888 KB Output is correct
28 Correct 2565 ms 265360 KB Output is correct
29 Correct 6517 ms 259420 KB Output is correct
30 Correct 6593 ms 282920 KB Output is correct
31 Correct 6759 ms 283476 KB Output is correct
32 Correct 2506 ms 226248 KB Output is correct
33 Correct 1924 ms 220672 KB Output is correct
34 Correct 2663 ms 204600 KB Output is correct
35 Correct 2744 ms 203972 KB Output is correct
36 Correct 3667 ms 205404 KB Output is correct
37 Correct 3623 ms 204956 KB Output is correct