oj.uz

답안 #924842

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
924842 2024-02-09T22:31:09 Z beaconmc 공장들 (JOI14_factories) C++14
100 / 100
 6813 ms 300548 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];
     
    ll timer = 0;
    ll start[max_n], endd[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){
      start[a] = timer++;
      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]);
      }
      endd[a] = timer;
    }
     
    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 (start[stack[stack.size()-1]] <= start[i.second] && endd[stack[stack.size()-1]] >= endd[i.second]){
            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

# 결과 실행 시간 메모리 Grader output
1 Correct 65 ms 124072 KB Output is correct
2 Correct 1063 ms 138760 KB Output is correct
3 Correct 1220 ms 138592 KB Output is correct
4 Correct 1161 ms 139024 KB Output is correct
5 Correct 1014 ms 139132 KB Output is correct
6 Correct 713 ms 138320 KB Output is correct
7 Correct 1222 ms 138836 KB Output is correct
8 Correct 1153 ms 138840 KB Output is correct
9 Correct 985 ms 139132 KB Output is correct
10 Correct 726 ms 138520 KB Output is correct
11 Correct 1214 ms 138636 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 123740 KB Output is correct
2 Correct 1850 ms 238704 KB Output is correct
3 Correct 3703 ms 245932 KB Output is correct
4 Correct 1173 ms 232452 KB Output is correct
5 Correct 4119 ms 288704 KB Output is correct
6 Correct 3849 ms 247192 KB Output is correct
7 Correct 2497 ms 161296 KB Output is correct
8 Correct 954 ms 158632 KB Output is correct
9 Correct 2817 ms 169400 KB Output is correct
10 Correct 2373 ms 162116 KB Output is correct

Subtask #3
67.0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 65 ms 124072 KB Output is correct
2 Correct 1063 ms 138760 KB Output is correct
3 Correct 1220 ms 138592 KB Output is correct
4 Correct 1161 ms 139024 KB Output is correct
5 Correct 1014 ms 139132 KB Output is correct
6 Correct 713 ms 138320 KB Output is correct
7 Correct 1222 ms 138836 KB Output is correct
8 Correct 1153 ms 138840 KB Output is correct
9 Correct 985 ms 139132 KB Output is correct
10 Correct 726 ms 138520 KB Output is correct
11 Correct 1214 ms 138636 KB Output is correct
12 Correct 30 ms 123740 KB Output is correct
13 Correct 1850 ms 238704 KB Output is correct
14 Correct 3703 ms 245932 KB Output is correct
15 Correct 1173 ms 232452 KB Output is correct
16 Correct 4119 ms 288704 KB Output is correct
17 Correct 3849 ms 247192 KB Output is correct
18 Correct 2497 ms 161296 KB Output is correct
19 Correct 954 ms 158632 KB Output is correct
20 Correct 2817 ms 169400 KB Output is correct
21 Correct 2373 ms 162116 KB Output is correct
22 Correct 3970 ms 264504 KB Output is correct
23 Correct 3505 ms 264444 KB Output is correct
24 Correct 5359 ms 274128 KB Output is correct
25 Correct 5356 ms 274992 KB Output is correct
26 Correct 6813 ms 255528 KB Output is correct
27 Correct 5418 ms 300548 KB Output is correct
28 Correct 1986 ms 248760 KB Output is correct
29 Correct 6494 ms 253352 KB Output is correct
30 Correct 6388 ms 252628 KB Output is correct
31 Correct 6450 ms 253392 KB Output is correct
32 Correct 2286 ms 177752 KB Output is correct
33 Correct 1182 ms 167728 KB Output is correct
34 Correct 2055 ms 160672 KB Output is correct
35 Correct 1971 ms 160476 KB Output is correct
36 Correct 2884 ms 162024 KB Output is correct
37 Correct 2707 ms 161952 KB Output is correct