oj.uz

답안 #831976

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
831976 2023-08-20T18:59:30 Z beaconmc 공장들 (JOI14_factories) C++14
33 / 100
 8000 ms 258876 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;
  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

# 결과 실행 시간 메모리 Grader output
1 Correct 79 ms 102516 KB Output is correct
2 Correct 2052 ms 112020 KB Output is correct
3 Correct 2492 ms 113012 KB Output is correct
4 Correct 2237 ms 113760 KB Output is correct
5 Correct 1934 ms 113648 KB Output is correct
6 Correct 1463 ms 113040 KB Output is correct
7 Correct 2661 ms 113036 KB Output is correct
8 Correct 2243 ms 113676 KB Output is correct
9 Correct 1864 ms 113620 KB Output is correct
10 Correct 1422 ms 113052 KB Output is correct
11 Correct 2590 ms 112924 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 102276 KB Output is correct
2 Correct 2632 ms 202576 KB Output is correct
3 Correct 5685 ms 209568 KB Output is correct
4 Correct 1435 ms 196988 KB Output is correct
5 Correct 4542 ms 252388 KB Output is correct
6 Correct 5878 ms 210768 KB Output is correct
7 Correct 4787 ms 132104 KB Output is correct
8 Correct 1518 ms 130000 KB Output is correct
9 Correct 4021 ms 140368 KB Output is correct
10 Correct 4692 ms 133196 KB Output is correct

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 79 ms 102516 KB Output is correct
2 Correct 2052 ms 112020 KB Output is correct
3 Correct 2492 ms 113012 KB Output is correct
4 Correct 2237 ms 113760 KB Output is correct
5 Correct 1934 ms 113648 KB Output is correct
6 Correct 1463 ms 113040 KB Output is correct
7 Correct 2661 ms 113036 KB Output is correct
8 Correct 2243 ms 113676 KB Output is correct
9 Correct 1864 ms 113620 KB Output is correct
10 Correct 1422 ms 113052 KB Output is correct
11 Correct 2590 ms 112924 KB Output is correct
12 Correct 38 ms 102276 KB Output is correct
13 Correct 2632 ms 202576 KB Output is correct
14 Correct 5685 ms 209568 KB Output is correct
15 Correct 1435 ms 196988 KB Output is correct
16 Correct 4542 ms 252388 KB Output is correct
17 Correct 5878 ms 210768 KB Output is correct
18 Correct 4787 ms 132104 KB Output is correct
19 Correct 1518 ms 130000 KB Output is correct
20 Correct 4021 ms 140368 KB Output is correct
21 Correct 4692 ms 133196 KB Output is correct
22 Correct 7489 ms 257148 KB Output is correct
23 Execution timed out 8016 ms 258876 KB Time limit exceeded
24 Halted 0 ms 0 KB -