oj.uz

Submission #653223

# Submission time Handle Problem Language Result Execution time Memory
653223 2022-10-26T08:57:31 Z beaconmc Factories (JOI14_factories) C++14
100 / 100
 7937 ms 131512 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include "factories.h"
#include <bits/stdc++.h>

#define ll long long
#define FOR(i,x,y) for(ll i=x; i<y; i++)

using namespace std;


bool r[600000];
vector<pair<ll,ll>> edges[600000];
ll sub[600000], par[600000], ans[600000];
ll n,m,root;

ll first[600000];
ll dists[600000];
vector<ll> euler;
vector<ll> updated;


void dfs2(ll a, ll p, ll v){
  first[a] = euler.size();
  euler.push_back(a);
  for (auto&i : edges[a]){
    if (i.first!=p){ 
      dfs2(i.first, a, v+i.second);
      euler.push_back(a);
    }
    
  }
  dists[a] = v;
}

int distmin(ll a, ll b){
  if (dists[a] < dists[b]){
    return a;
  }else{
    return b;
  }
}


int t[2*1048576];

void build() {
    for (int i=1048576-1;i>0;--i)
        t[i]=distmin(t[i<<1],t[i<<1|1]);
}

int query(int l,int r) {
    int minV=0;
    for (l+=1048576,r+=1048576;l<r;l>>=1,r>>=1) {

        if (l&1){
          minV=distmin(minV,t[l++]);

        }

        if (r&1){
          minV=distmin(minV,t[--r]);

        }
    }

    return minV;
}
 



ll dfs(ll a, ll p){

  sub[a] = 1;
  for (auto& i : edges[a]){
    if (i.first!=p && !r[i.first]) sub[a] += dfs(i.first, a);
  }
  return sub[a];
}

ll centroid(ll a, ll sz, ll p){

  for (auto&i : edges[a]){
    if (i.first!=p && !r[i.first] && sub[i.first]*2 > sz){
      return centroid(i.first, sz, a);
    }
  }
  return a;
}

void decomp(ll a, ll p){
  ll c = centroid(a, dfs(a, -1), -1);

  if (p!=-1){
    par[c] = p;
  }else{
    par[c] = -1;
  }




  r[c] = 1;
  for (auto&i : edges[c]){
    if (!r[i.first]) decomp(i.first, c);
  }
}

ll dist(ll a, ll b){
  if (first[a] > first[b]) swap(a,b);

  return dists[a] + dists[b] - 2*dists[query(first[a],first[b])];
}

void update(ll a){
  ll orig = a;
  ans[a] = 0;
  updated.push_back(a);
  ll distance = 0;

  while (par[a] != -1){
    distance = dist(orig, par[a]);

    a = par[a];
    
    ans[a] = min(ans[a], distance);
    updated.push_back(a);
  }
}

ll query(ll a){
  ll orig = a;
  ll distance = 0;
  ll tempans = 1000000000000000;

  tempans = min(tempans, ans[a]);


  while (par[a] != -1){
    distance = dist(orig, par[a]);
    a = par[a];
    tempans = min(tempans, distance + ans[a]);
  }
  return tempans;
}


void Init(int N, int A[], int B[], int D[]) {
  FOR(i,0,1048576) t[i] = 0;
  FOR(i,0,600000) sub[i] = 0, r[i] = 0, ans[i] = 1000000000000000;
  n = N;
  dists[0] = 1000000000000000;

  FOR(i,0,n-1){
    ll a,b,c;
    a = A[i]+1;
    b = B[i]+1;
    c = D[i];
    edges[a].push_back({b,c});
    edges[b].push_back({a,c});
  }
  dfs2(1,-1,0);

  FOR(i,0,euler.size()){
    t[i+1048576] =  euler[i];
  }
  build();



  decomp(1,-1);

}



long long Query(int S, int X[], int T, int Y[]) {
  updated.clear();
  ll anss = 1000000000000000;

  FOR(i,0,S){
    update(X[i]+1);
  }
  

  FOR(i,0,T){
    anss = min(anss, (ll) query(Y[i]+1));
  }
  for (auto&i : updated){
    ans[i] = 1000000000000000;
  }


  return anss;
}

Compilation message

factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:8:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define FOR(i,x,y) for(ll i=x; i<y; i++)
......
  166 |   FOR(i,0,euler.size()){
      |       ~~~~~~~~~~~~~~~~           
factories.cpp:166:3: note: in expansion of macro 'FOR'
  166 |   FOR(i,0,euler.size()){
      |   ^~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 28816 KB Output is correct
2 Correct 1190 ms 37208 KB Output is correct
3 Correct 1859 ms 37296 KB Output is correct
4 Correct 1813 ms 37720 KB Output is correct
5 Correct 1645 ms 37768 KB Output is correct
6 Correct 339 ms 37096 KB Output is correct
7 Correct 1749 ms 37180 KB Output is correct
8 Correct 1876 ms 37196 KB Output is correct
9 Correct 1600 ms 37684 KB Output is correct
10 Correct 344 ms 37084 KB Output is correct
11 Correct 1740 ms 37236 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 28648 KB Output is correct
2 Correct 3137 ms 90600 KB Output is correct
3 Correct 4604 ms 94560 KB Output is correct
4 Correct 729 ms 88180 KB Output is correct
5 Correct 4999 ms 124996 KB Output is correct
6 Correct 5164 ms 95704 KB Output is correct
7 Correct 4078 ms 50004 KB Output is correct
8 Correct 508 ms 49440 KB Output is correct
9 Correct 3360 ms 54576 KB Output is correct
10 Correct 3956 ms 51136 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 28816 KB Output is correct
2 Correct 1190 ms 37208 KB Output is correct
3 Correct 1859 ms 37296 KB Output is correct
4 Correct 1813 ms 37720 KB Output is correct
5 Correct 1645 ms 37768 KB Output is correct
6 Correct 339 ms 37096 KB Output is correct
7 Correct 1749 ms 37180 KB Output is correct
8 Correct 1876 ms 37196 KB Output is correct
9 Correct 1600 ms 37684 KB Output is correct
10 Correct 344 ms 37084 KB Output is correct
11 Correct 1740 ms 37236 KB Output is correct
12 Correct 24 ms 28648 KB Output is correct
13 Correct 3137 ms 90600 KB Output is correct
14 Correct 4604 ms 94560 KB Output is correct
15 Correct 729 ms 88180 KB Output is correct
16 Correct 4999 ms 124996 KB Output is correct
17 Correct 5164 ms 95704 KB Output is correct
18 Correct 4078 ms 50004 KB Output is correct
19 Correct 508 ms 49440 KB Output is correct
20 Correct 3360 ms 54576 KB Output is correct
21 Correct 3956 ms 51136 KB Output is correct
22 Correct 4494 ms 99868 KB Output is correct
23 Correct 4804 ms 104696 KB Output is correct
24 Correct 7365 ms 108224 KB Output is correct
25 Correct 7600 ms 109868 KB Output is correct
26 Correct 7937 ms 96592 KB Output is correct
27 Correct 7617 ms 131512 KB Output is correct
28 Correct 1018 ms 93724 KB Output is correct
29 Correct 7409 ms 95908 KB Output is correct
30 Correct 7475 ms 119700 KB Output is correct
31 Correct 7449 ms 120272 KB Output is correct
32 Correct 3245 ms 75324 KB Output is correct
33 Correct 515 ms 65724 KB Output is correct
34 Correct 2377 ms 61336 KB Output is correct
35 Correct 2585 ms 61104 KB Output is correct
36 Correct 3798 ms 62136 KB Output is correct
37 Correct 3723 ms 62016 KB Output is correct