oj.uz

Submission #831981

# Submission time Handle Problem Language Result Execution time Memory
831981 2023-08-20T19:03:05 Z beaconmc Factories (JOI14_factories) C++14
33 / 100
 8000 ms 252480 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);
}

unordered_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;
  unordered_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 77 ms 102448 KB Output is correct
2 Correct 2040 ms 111708 KB Output is correct
3 Correct 2571 ms 111332 KB Output is correct
4 Correct 2289 ms 112072 KB Output is correct
5 Correct 1897 ms 112092 KB Output is correct
6 Correct 1558 ms 111536 KB Output is correct
7 Correct 2848 ms 111368 KB Output is correct
8 Correct 2315 ms 112060 KB Output is correct
9 Correct 1859 ms 112060 KB Output is correct
10 Correct 1556 ms 111508 KB Output is correct
11 Correct 2938 ms 111368 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 102312 KB Output is correct
2 Correct 3078 ms 202600 KB Output is correct
3 Correct 5909 ms 209584 KB Output is correct
4 Correct 1687 ms 196892 KB Output is correct
5 Correct 5034 ms 252480 KB Output is correct
6 Correct 7889 ms 210972 KB Output is correct
7 Correct 6038 ms 132352 KB Output is correct
8 Correct 2090 ms 130232 KB Output is correct
9 Correct 4966 ms 140532 KB Output is correct
10 Correct 5472 ms 133472 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 102448 KB Output is correct
2 Correct 2040 ms 111708 KB Output is correct
3 Correct 2571 ms 111332 KB Output is correct
4 Correct 2289 ms 112072 KB Output is correct
5 Correct 1897 ms 112092 KB Output is correct
6 Correct 1558 ms 111536 KB Output is correct
7 Correct 2848 ms 111368 KB Output is correct
8 Correct 2315 ms 112060 KB Output is correct
9 Correct 1859 ms 112060 KB Output is correct
10 Correct 1556 ms 111508 KB Output is correct
11 Correct 2938 ms 111368 KB Output is correct
12 Correct 42 ms 102312 KB Output is correct
13 Correct 3078 ms 202600 KB Output is correct
14 Correct 5909 ms 209584 KB Output is correct
15 Correct 1687 ms 196892 KB Output is correct
16 Correct 5034 ms 252480 KB Output is correct
17 Correct 7889 ms 210972 KB Output is correct
18 Correct 6038 ms 132352 KB Output is correct
19 Correct 2090 ms 130232 KB Output is correct
20 Correct 4966 ms 140532 KB Output is correct
21 Correct 5472 ms 133472 KB Output is correct
22 Correct 7561 ms 233612 KB Output is correct
23 Execution timed out 8063 ms 233484 KB Time limit exceeded
24 Halted 0 ms 0 KB -