oj.uz

Submission #831991

# Submission time Handle Problem Language Result Execution time Memory
831991 2023-08-20T19:23:09 Z beaconmc Factories (JOI14_factories) C++14
33 / 100
 8000 ms 264680 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);
}
 
bool firsts[max_n], seconds[max_n];
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[a]) ans1 = 0;
  if (firsts[a]) ans2 = 0;
  dp[a] = ans1;
  dp2[a] = ans2;
  
}
 
 
 
long long Query(int S, int X[], int T, int Y[]) {

 
  vector<vector<ll>> special;

  FOR(i,0,S) special.push_back({t[X[i]], X[i]});
  FOR(i,0,T) 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 : special) firsts[i[1]] = 0, seconds[i[1]] = 0;
  for (auto&i : stuff) firsts[i] = 0, seconds[i] = 0;
  FOR(i,0,S) firsts[X[i]] = 1;
  FOR(i,0,T) seconds[Y[i]] = 1;

  for (auto&i : stuff){
    if (firsts[i] || seconds[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 74 ms 102516 KB Output is correct
2 Correct 2020 ms 111624 KB Output is correct
3 Correct 2336 ms 111616 KB Output is correct
4 Correct 2103 ms 111988 KB Output is correct
5 Correct 1776 ms 112052 KB Output is correct
6 Correct 1363 ms 111484 KB Output is correct
7 Correct 2422 ms 111492 KB Output is correct
8 Correct 2127 ms 112040 KB Output is correct
9 Correct 1773 ms 111940 KB Output is correct
10 Correct 1374 ms 111384 KB Output is correct
11 Correct 2341 ms 111360 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 102272 KB Output is correct
2 Correct 2479 ms 203576 KB Output is correct
3 Correct 5639 ms 210644 KB Output is correct
4 Correct 1406 ms 197868 KB Output is correct
5 Correct 4894 ms 253436 KB Output is correct
6 Correct 6074 ms 211724 KB Output is correct
7 Correct 4983 ms 132296 KB Output is correct
8 Correct 1473 ms 130232 KB Output is correct
9 Correct 3860 ms 140544 KB Output is correct
10 Correct 4683 ms 133400 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 102516 KB Output is correct
2 Correct 2020 ms 111624 KB Output is correct
3 Correct 2336 ms 111616 KB Output is correct
4 Correct 2103 ms 111988 KB Output is correct
5 Correct 1776 ms 112052 KB Output is correct
6 Correct 1363 ms 111484 KB Output is correct
7 Correct 2422 ms 111492 KB Output is correct
8 Correct 2127 ms 112040 KB Output is correct
9 Correct 1773 ms 111940 KB Output is correct
10 Correct 1374 ms 111384 KB Output is correct
11 Correct 2341 ms 111360 KB Output is correct
12 Correct 38 ms 102272 KB Output is correct
13 Correct 2479 ms 203576 KB Output is correct
14 Correct 5639 ms 210644 KB Output is correct
15 Correct 1406 ms 197868 KB Output is correct
16 Correct 4894 ms 253436 KB Output is correct
17 Correct 6074 ms 211724 KB Output is correct
18 Correct 4983 ms 132296 KB Output is correct
19 Correct 1473 ms 130232 KB Output is correct
20 Correct 3860 ms 140544 KB Output is correct
21 Correct 4683 ms 133400 KB Output is correct
22 Correct 6617 ms 230480 KB Output is correct
23 Correct 5573 ms 231860 KB Output is correct
24 Execution timed out 8029 ms 264680 KB Time limit exceeded
25 Halted 0 ms 0 KB -