oj.uz

Submission #653216

# Submission time Handle Problem Language Result Execution time Memory
653216 2022-10-26T08:52:47 Z beaconmc Factories (JOI14_factories) C++14
15 / 100
 1686 ms 171856 KB 
#pragma gcc optimize ( unroll-loops )
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
#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*524288];

void build() {
    for (int i=524288-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+=524288,r+=524288;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+524288] =  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:1: warning: ignoring '#pragma gcc optimize' [-Wunknown-pragmas]
    1 | #pragma gcc optimize ( unroll-loops )
      | 
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 29020 KB Output is correct
2 Correct 1098 ms 37672 KB Output is correct
3 Correct 1668 ms 37756 KB Output is correct
4 Correct 1661 ms 38184 KB Output is correct
5 Correct 1512 ms 38228 KB Output is correct
6 Correct 324 ms 37584 KB Output is correct
7 Correct 1627 ms 37740 KB Output is correct
8 Correct 1686 ms 37628 KB Output is correct
9 Correct 1534 ms 38164 KB Output is correct
10 Correct 320 ms 37592 KB Output is correct
11 Correct 1604 ms 37796 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 28628 KB Output is correct
2 Runtime error 943 ms 171856 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 29020 KB Output is correct
2 Correct 1098 ms 37672 KB Output is correct
3 Correct 1668 ms 37756 KB Output is correct
4 Correct 1661 ms 38184 KB Output is correct
5 Correct 1512 ms 38228 KB Output is correct
6 Correct 324 ms 37584 KB Output is correct
7 Correct 1627 ms 37740 KB Output is correct
8 Correct 1686 ms 37628 KB Output is correct
9 Correct 1534 ms 38164 KB Output is correct
10 Correct 320 ms 37592 KB Output is correct
11 Correct 1604 ms 37796 KB Output is correct
12 Correct 16 ms 28628 KB Output is correct
13 Runtime error 943 ms 171856 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -