oj.uz

Submission #831955

# Submission time Handle Problem Language Result Execution time Memory
831955 2023-08-20T18:34:11 Z beaconmc Factories (JOI14_factories) C++11
0 / 100
 8000 ms 241260 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;
  FOR(i,0,top){
    ll ancestor = lca(special[i][1], special[i+1][1]);
    special.push_back({t[ancestor], ancestor});
  }

  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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3843 ms 102676 KB Output is correct
2 Execution timed out 8037 ms 111312 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 102288 KB Output is correct
2 Correct 2568 ms 202608 KB Output is correct
3 Correct 5595 ms 210872 KB Output is correct
4 Correct 1475 ms 196988 KB Output is correct
5 Execution timed out 8074 ms 241260 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 3843 ms 102676 KB Output is correct
2 Execution timed out 8037 ms 111312 KB Time limit exceeded
3 Halted 0 ms 0 KB -