oj.uz

Submission #831982

# Submission time Handle Problem Language Result Execution time Memory
831982 2023-08-20T19:04:19 Z beaconmc Factories (JOI14_factories) C++14
33 / 100
 8000 ms 252404 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

typedef long long ll;
using namespace std;
//using namespace __gnu_pbds;

#define FOR(i, x, y) for(ll i=x; i<y; i++)
#define FORNEG(i, x, y) for(ll i=x; i>y; i--)
//#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)

#include "factories.h"

const ll max_n = 500001;
ll dp[max_n], dp2[max_n], par[max_n], ancc[max_n][20], fdepth[max_n], depth[max_n], t[max_n];

vector<vector<ll>> edges[max_n];

ll n;

ll anc(ll a, ll jump){
  if (ancc[a][jump] != -1) return ancc[a][jump];
  if (fdepth[a] <= (1<<jump)) return 0;
  if (jump==0) return par[a];

  ancc[a][jump] = anc(anc(a, jump-1), jump-1);
  return ancc[a][jump];
}

ll lca (ll a, ll b){
  if (fdepth[a] < fdepth[b]) swap(a,b);
  
  FORNEG(i,19,-1) if (fdepth[anc(a,i)] >= fdepth[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];
}

ll tt = 0;
void initdfs(ll a, ll p, ll d, ll dd){
  t[a] = tt++;
  par[a] = p;
  fdepth[a] = d;
  depth[a] = dd;
  for (auto&i : edges[a]){
    if (i[0]!=p) initdfs(i[0], a, d+1, dd+i[1]);
  }
}

void Init(int N, int A[], int B[], int D[]) {

  n = N;
  FOR(i,0,N) dp[i] = 0,dp2[i] = 0;
  FOR(i,0,max_n) FOR(j,0,20) ancc[i][j] = -1;


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

set<ll> firsts, seconds;
vector<vector<ll>> redges[max_n];

void dfs(ll a, ll p){
  ll ans1 = 1000000000000000;
  ll ans2 = 1000000000000000;

  for (auto&i : redges[a]){
    if (i[0]==p) continue;
    dfs(i[0], a);
    ans1 = min(ans1, dp[i[0]] + i[1]);
    ans2 = min(ans2, dp2[i[0]] + i[1]);
  }
  if (seconds.count(a)) ans1 = 0;
  if (firsts.count(a)) ans2 = 0;
  dp[a] = ans1;
  dp2[a] = ans2;
  
}



long long Query(int S, int X[], int T, int Y[]) {



  vector<vector<ll>> special;
  firsts.clear();
  seconds.clear();

  FOR(i,0,S) firsts.insert(X[i]), special.push_back({t[X[i]], X[i]});
  FOR(i,0,T) seconds.insert(Y[i]), special.push_back({t[Y[i]], Y[i]});


  sort(special.begin(), special.end());
  ll top = special.size()-1;
  set<ll> stuff;
  FOR(i,0,top){
    ll ancestor = lca(special[i][1], special[i+1][1]);
    stuff.insert(ancestor);
    //special.push_back({t[ancestor], ancestor});
  }
  for (auto&i : stuff){
    if (firsts.count(i) || seconds.count(i)) continue;
    special.push_back({t[i], i});
  }

  for (auto&i : special) redges[i[1]].clear();

  sort(special.begin(), special.end());

  vector<ll> stack;

  for (auto&i : special){
    dp[i[1]] = 1000000000000000;
    dp2[i[1]] = 1000000000000000;
  }
  ll root = special[0][1];



  for (auto&i : special){
    while (stack.size()){
      if (stack[stack.size()-1] == i[1])stack.pop_back();
      else if (lca(stack[stack.size()-1], i[1]) == stack[stack.size()-1]){
        redges[stack[stack.size()-1]].push_back({i[1], depth[i[1]] - depth[stack[stack.size()-1]]});
        break;
      }else{
        stack.pop_back();
      }
    }
    stack.push_back(i[1]);
  }




  dfs(root, -1);
  ll ans = 1000000000000000;
  for (auto&i : special){
    ans = min(ans, dp[i[1]] + dp2[i[1]]);
  }






  return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 102720 KB Output is correct
2 Correct 2544 ms 112160 KB Output is correct
3 Correct 2987 ms 111688 KB Output is correct
4 Correct 2719 ms 112380 KB Output is correct
5 Correct 2361 ms 112432 KB Output is correct
6 Correct 1752 ms 111836 KB Output is correct
7 Correct 2958 ms 111732 KB Output is correct
8 Correct 2707 ms 112500 KB Output is correct
9 Correct 2331 ms 112456 KB Output is correct
10 Correct 1797 ms 111892 KB Output is correct
11 Correct 2884 ms 111708 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 102332 KB Output is correct
2 Correct 2730 ms 202732 KB Output is correct
3 Correct 5862 ms 209732 KB Output is correct
4 Correct 1479 ms 196828 KB Output is correct
5 Correct 4890 ms 252404 KB Output is correct
6 Correct 6186 ms 210816 KB Output is correct
7 Correct 5393 ms 132080 KB Output is correct
8 Correct 1661 ms 130036 KB Output is correct
9 Correct 4389 ms 140600 KB Output is correct
10 Correct 5182 ms 133328 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 102720 KB Output is correct
2 Correct 2544 ms 112160 KB Output is correct
3 Correct 2987 ms 111688 KB Output is correct
4 Correct 2719 ms 112380 KB Output is correct
5 Correct 2361 ms 112432 KB Output is correct
6 Correct 1752 ms 111836 KB Output is correct
7 Correct 2958 ms 111732 KB Output is correct
8 Correct 2707 ms 112500 KB Output is correct
9 Correct 2331 ms 112456 KB Output is correct
10 Correct 1797 ms 111892 KB Output is correct
11 Correct 2884 ms 111708 KB Output is correct
12 Correct 46 ms 102332 KB Output is correct
13 Correct 2730 ms 202732 KB Output is correct
14 Correct 5862 ms 209732 KB Output is correct
15 Correct 1479 ms 196828 KB Output is correct
16 Correct 4890 ms 252404 KB Output is correct
17 Correct 6186 ms 210816 KB Output is correct
18 Correct 5393 ms 132080 KB Output is correct
19 Correct 1661 ms 130036 KB Output is correct
20 Correct 4389 ms 140600 KB Output is correct
21 Correct 5182 ms 133328 KB Output is correct
22 Execution timed out 8029 ms 233220 KB Time limit exceeded
23 Halted 0 ms 0 KB -