oj.uz

Submission #924850

# Submission time Handle Problem Language Result Execution time Memory
924850 2024-02-09T22:46:03 Z beaconmc Factories (JOI14_factories) C++14
33 / 100
 8000 ms 271892 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 (lca(stack[stack.size()-1], i.second) == stack[stack.size()-1]){
            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 55 ms 133884 KB Output is correct
2 Correct 1711 ms 139420 KB Output is correct
3 Correct 2125 ms 139092 KB Output is correct
4 Correct 1857 ms 139620 KB Output is correct
5 Correct 1519 ms 139616 KB Output is correct
6 Correct 1104 ms 139020 KB Output is correct
7 Correct 2077 ms 138904 KB Output is correct
8 Correct 1820 ms 139744 KB Output is correct
9 Correct 1484 ms 139628 KB Output is correct
10 Correct 1163 ms 139092 KB Output is correct
11 Correct 2071 ms 139292 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 133980 KB Output is correct
2 Correct 2156 ms 222060 KB Output is correct
3 Correct 4566 ms 230160 KB Output is correct
4 Correct 1200 ms 216280 KB Output is correct
5 Correct 4067 ms 271892 KB Output is correct
6 Correct 4769 ms 230180 KB Output is correct
7 Correct 3761 ms 160560 KB Output is correct
8 Correct 1329 ms 157464 KB Output is correct
9 Correct 3327 ms 168104 KB Output is correct
10 Correct 3989 ms 160732 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 133884 KB Output is correct
2 Correct 1711 ms 139420 KB Output is correct
3 Correct 2125 ms 139092 KB Output is correct
4 Correct 1857 ms 139620 KB Output is correct
5 Correct 1519 ms 139616 KB Output is correct
6 Correct 1104 ms 139020 KB Output is correct
7 Correct 2077 ms 138904 KB Output is correct
8 Correct 1820 ms 139744 KB Output is correct
9 Correct 1484 ms 139628 KB Output is correct
10 Correct 1163 ms 139092 KB Output is correct
11 Correct 2071 ms 139292 KB Output is correct
12 Correct 22 ms 133980 KB Output is correct
13 Correct 2156 ms 222060 KB Output is correct
14 Correct 4566 ms 230160 KB Output is correct
15 Correct 1200 ms 216280 KB Output is correct
16 Correct 4067 ms 271892 KB Output is correct
17 Correct 4769 ms 230180 KB Output is correct
18 Correct 3761 ms 160560 KB Output is correct
19 Correct 1329 ms 157464 KB Output is correct
20 Correct 3327 ms 168104 KB Output is correct
21 Correct 3989 ms 160732 KB Output is correct
22 Correct 5266 ms 242284 KB Output is correct
23 Correct 4407 ms 241548 KB Output is correct
24 Correct 6838 ms 251492 KB Output is correct
25 Correct 6992 ms 252568 KB Output is correct
26 Execution timed out 8055 ms 233596 KB Time limit exceeded
27 Halted 0 ms 0 KB -