oj.uz

Submission #924848

# Submission time Handle Problem Language Result Execution time Memory
924848 2024-02-09T22:42:04 Z beaconmc Factories (JOI14_factories) C++14
100 / 100
 5869 ms 296528 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(start[X[i]], X[i]));
      FOR(i,0,T) special.push_back(make_pair(start[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({start[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 (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

# Verdict Execution time Memory Grader output
1 Correct 54 ms 134056 KB Output is correct
2 Correct 1034 ms 147944 KB Output is correct
3 Correct 1199 ms 147856 KB Output is correct
4 Correct 1181 ms 148372 KB Output is correct
5 Correct 992 ms 148320 KB Output is correct
6 Correct 711 ms 147932 KB Output is correct
7 Correct 1246 ms 147776 KB Output is correct
8 Correct 1206 ms 148556 KB Output is correct
9 Correct 961 ms 148452 KB Output is correct
10 Correct 714 ms 147716 KB Output is correct
11 Correct 1217 ms 147772 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 133968 KB Output is correct
2 Correct 1856 ms 238716 KB Output is correct
3 Correct 3321 ms 246772 KB Output is correct
4 Correct 1070 ms 232884 KB Output is correct
5 Correct 3677 ms 288592 KB Output is correct
6 Correct 3374 ms 246828 KB Output is correct
7 Correct 2198 ms 173004 KB Output is correct
8 Correct 896 ms 170016 KB Output is correct
9 Correct 2425 ms 180324 KB Output is correct
10 Correct 2172 ms 173684 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 134056 KB Output is correct
2 Correct 1034 ms 147944 KB Output is correct
3 Correct 1199 ms 147856 KB Output is correct
4 Correct 1181 ms 148372 KB Output is correct
5 Correct 992 ms 148320 KB Output is correct
6 Correct 711 ms 147932 KB Output is correct
7 Correct 1246 ms 147776 KB Output is correct
8 Correct 1206 ms 148556 KB Output is correct
9 Correct 961 ms 148452 KB Output is correct
10 Correct 714 ms 147716 KB Output is correct
11 Correct 1217 ms 147772 KB Output is correct
12 Correct 29 ms 133968 KB Output is correct
13 Correct 1856 ms 238716 KB Output is correct
14 Correct 3321 ms 246772 KB Output is correct
15 Correct 1070 ms 232884 KB Output is correct
16 Correct 3677 ms 288592 KB Output is correct
17 Correct 3374 ms 246828 KB Output is correct
18 Correct 2198 ms 173004 KB Output is correct
19 Correct 896 ms 170016 KB Output is correct
20 Correct 2425 ms 180324 KB Output is correct
21 Correct 2172 ms 173684 KB Output is correct
22 Correct 3656 ms 263796 KB Output is correct
23 Correct 3240 ms 263756 KB Output is correct
24 Correct 4965 ms 272836 KB Output is correct
25 Correct 5136 ms 274612 KB Output is correct
26 Correct 5869 ms 252872 KB Output is correct
27 Correct 4680 ms 296528 KB Output is correct
28 Correct 1825 ms 245248 KB Output is correct
29 Correct 5636 ms 249724 KB Output is correct
30 Correct 5595 ms 249276 KB Output is correct
31 Correct 5814 ms 249256 KB Output is correct
32 Correct 2093 ms 186992 KB Output is correct
33 Correct 1095 ms 172796 KB Output is correct
34 Correct 1981 ms 167408 KB Output is correct
35 Correct 1876 ms 167592 KB Output is correct
36 Correct 2613 ms 168828 KB Output is correct
37 Correct 2613 ms 161904 KB Output is correct