oj.uz

Submission #831997

# Submission time Handle Problem Language Result Execution time Memory
831997 2023-08-20T19:26:42 Z beaconmc Factories (JOI14_factories) C++14
33 / 100
 8000 ms 261816 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<pair<ll,ll>> special;

  FOR(i,0,S) special.push_back(make_pair(t[X[i]], X[i]));
  FOR(i,0,T) special.push_back(make_pair(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].second, special[i+1].second);
    stuff.insert(ancestor);
    //special.push_back({t[ancestor], ancestor});
  }
  for (auto&i : special) firsts[i.second] = 0, seconds[i.second] = 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.second].clear();
 
  sort(special.begin(), special.end());
 
  vector<ll> stack;
 
  for (auto&i : special){
    dp[i.second] = 1000000000000000;
    dp2[i.second] = 1000000000000000;
  }
  ll root = special[0].second;
 
 
 
  for (auto&i : special){
    while (stack.size()){
      if (stack[stack.size()-1] == i.second)stack.pop_back();
      else if (lca(stack[stack.size()-1], i.second) == stack[stack.size()-1]){
        redges[stack[stack.size()-1]].push_back({i.second, depth[i.second] - depth[stack[stack.size()-1]]});
        break;
      }else{
        stack.pop_back();
      }
    }
    stack.push_back(i.second);
  }
 
 
 
 
  dfs(root, -1);
  ll ans = 1000000000000000;
  for (auto&i : special){
    ans = min(ans, dp[i.second] + dp2[i.second]);
  }
 
 
 
 
 
 
  return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 102404 KB Output is correct
2 Correct 1629 ms 111464 KB Output is correct
3 Correct 2064 ms 111444 KB Output is correct
4 Correct 1863 ms 111712 KB Output is correct
5 Correct 1520 ms 111952 KB Output is correct
6 Correct 1132 ms 111308 KB Output is correct
7 Correct 2100 ms 111312 KB Output is correct
8 Correct 1946 ms 111720 KB Output is correct
9 Correct 1531 ms 111876 KB Output is correct
10 Correct 1146 ms 111376 KB Output is correct
11 Correct 2086 ms 111444 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 102220 KB Output is correct
2 Correct 2348 ms 203612 KB Output is correct
3 Correct 5325 ms 210600 KB Output is correct
4 Correct 1344 ms 197900 KB Output is correct
5 Correct 4505 ms 253392 KB Output is correct
6 Correct 5408 ms 211884 KB Output is correct
7 Correct 4397 ms 132496 KB Output is correct
8 Correct 1324 ms 130164 KB Output is correct
9 Correct 3650 ms 140532 KB Output is correct
10 Correct 4152 ms 133520 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 102404 KB Output is correct
2 Correct 1629 ms 111464 KB Output is correct
3 Correct 2064 ms 111444 KB Output is correct
4 Correct 1863 ms 111712 KB Output is correct
5 Correct 1520 ms 111952 KB Output is correct
6 Correct 1132 ms 111308 KB Output is correct
7 Correct 2100 ms 111312 KB Output is correct
8 Correct 1946 ms 111720 KB Output is correct
9 Correct 1531 ms 111876 KB Output is correct
10 Correct 1146 ms 111376 KB Output is correct
11 Correct 2086 ms 111444 KB Output is correct
12 Correct 44 ms 102220 KB Output is correct
13 Correct 2348 ms 203612 KB Output is correct
14 Correct 5325 ms 210600 KB Output is correct
15 Correct 1344 ms 197900 KB Output is correct
16 Correct 4505 ms 253392 KB Output is correct
17 Correct 5408 ms 211884 KB Output is correct
18 Correct 4397 ms 132496 KB Output is correct
19 Correct 1324 ms 130164 KB Output is correct
20 Correct 3650 ms 140532 KB Output is correct
21 Correct 4152 ms 133520 KB Output is correct
22 Correct 5335 ms 226116 KB Output is correct
23 Correct 4663 ms 227168 KB Output is correct
24 Correct 7328 ms 235260 KB Output is correct
25 Correct 7332 ms 261816 KB Output is correct
26 Execution timed out 8047 ms 241044 KB Time limit exceeded
27 Halted 0 ms 0 KB -