oj.uz

답안 #831983

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
831983 2023-08-20T19:05:54 Z beaconmc 공장들 (JOI14_factories) C++14
33 / 100
 8000 ms 252484 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 85 ms 102476 KB Output is correct
2 Correct 2017 ms 111920 KB Output is correct
3 Correct 2508 ms 111412 KB Output is correct
4 Correct 2252 ms 112176 KB Output is correct
5 Correct 1886 ms 112216 KB Output is correct
6 Correct 1429 ms 111624 KB Output is correct
7 Correct 2576 ms 111576 KB Output is correct
8 Correct 2268 ms 112068 KB Output is correct
9 Correct 1952 ms 112136 KB Output is correct
10 Correct 1434 ms 111624 KB Output is correct
11 Correct 2606 ms 111380 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 102220 KB Output is correct
2 Correct 2717 ms 202544 KB Output is correct
3 Correct 5847 ms 209652 KB Output is correct
4 Correct 1481 ms 196888 KB Output is correct
5 Correct 4819 ms 252484 KB Output is correct
6 Correct 6095 ms 210732 KB Output is correct
7 Correct 5347 ms 132252 KB Output is correct
8 Correct 1690 ms 130104 KB Output is correct
9 Correct 4367 ms 140336 KB Output is correct
10 Correct 5156 ms 133380 KB Output is correct

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 85 ms 102476 KB Output is correct
2 Correct 2017 ms 111920 KB Output is correct
3 Correct 2508 ms 111412 KB Output is correct
4 Correct 2252 ms 112176 KB Output is correct
5 Correct 1886 ms 112216 KB Output is correct
6 Correct 1429 ms 111624 KB Output is correct
7 Correct 2576 ms 111576 KB Output is correct
8 Correct 2268 ms 112068 KB Output is correct
9 Correct 1952 ms 112136 KB Output is correct
10 Correct 1434 ms 111624 KB Output is correct
11 Correct 2606 ms 111380 KB Output is correct
12 Correct 44 ms 102220 KB Output is correct
13 Correct 2717 ms 202544 KB Output is correct
14 Correct 5847 ms 209652 KB Output is correct
15 Correct 1481 ms 196888 KB Output is correct
16 Correct 4819 ms 252484 KB Output is correct
17 Correct 6095 ms 210732 KB Output is correct
18 Correct 5347 ms 132252 KB Output is correct
19 Correct 1690 ms 130104 KB Output is correct
20 Correct 4367 ms 140336 KB Output is correct
21 Correct 5156 ms 133380 KB Output is correct
22 Correct 7446 ms 232924 KB Output is correct
23 Execution timed out 8054 ms 234236 KB Time limit exceeded
24 Halted 0 ms 0 KB -