Submission #924842

#	Time	Username	Problem	Language	Result	Execution time	Memory
924842		beaconmc	Factories (JOI14_factories)	C++14	100 / 100	6813 ms	300548 KiB

factories

    #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 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67