oj.uz

Submission #653217

# Submission time Handle Problem Language Result Execution time Memory
653217 2022-10-26T08:53:33 Z beaconmc Factories (JOI14_factories) C++14
33 / 100
 8000 ms 150896 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*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: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 34 ms 28840 KB Output is correct
2 Correct 1091 ms 37324 KB Output is correct
3 Correct 1694 ms 37172 KB Output is correct
4 Correct 1591 ms 37596 KB Output is correct
5 Correct 1511 ms 37668 KB Output is correct
6 Correct 324 ms 37140 KB Output is correct
7 Correct 1613 ms 37336 KB Output is correct
8 Correct 1692 ms 37396 KB Output is correct
9 Correct 1515 ms 37696 KB Output is correct
10 Correct 311 ms 37196 KB Output is correct
11 Correct 1611 ms 37412 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 28628 KB Output is correct
2 Correct 2997 ms 90552 KB Output is correct
3 Correct 4465 ms 93492 KB Output is correct
4 Correct 753 ms 88216 KB Output is correct
5 Correct 5103 ms 118240 KB Output is correct
6 Correct 5082 ms 113660 KB Output is correct
7 Correct 4281 ms 63788 KB Output is correct
8 Correct 487 ms 63440 KB Output is correct
9 Correct 3369 ms 67880 KB Output is correct
10 Correct 4043 ms 64980 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 28840 KB Output is correct
2 Correct 1091 ms 37324 KB Output is correct
3 Correct 1694 ms 37172 KB Output is correct
4 Correct 1591 ms 37596 KB Output is correct
5 Correct 1511 ms 37668 KB Output is correct
6 Correct 324 ms 37140 KB Output is correct
7 Correct 1613 ms 37336 KB Output is correct
8 Correct 1692 ms 37396 KB Output is correct
9 Correct 1515 ms 37696 KB Output is correct
10 Correct 311 ms 37196 KB Output is correct
11 Correct 1611 ms 37412 KB Output is correct
12 Correct 18 ms 28628 KB Output is correct
13 Correct 2997 ms 90552 KB Output is correct
14 Correct 4465 ms 93492 KB Output is correct
15 Correct 753 ms 88216 KB Output is correct
16 Correct 5103 ms 118240 KB Output is correct
17 Correct 5082 ms 113660 KB Output is correct
18 Correct 4281 ms 63788 KB Output is correct
19 Correct 487 ms 63440 KB Output is correct
20 Correct 3369 ms 67880 KB Output is correct
21 Correct 4043 ms 64980 KB Output is correct
22 Correct 4738 ms 124156 KB Output is correct
23 Correct 4936 ms 129340 KB Output is correct
24 Correct 7865 ms 131776 KB Output is correct
25 Correct 7583 ms 133652 KB Output is correct
26 Correct 7811 ms 120196 KB Output is correct
27 Execution timed out 8036 ms 150896 KB Time limit exceeded
28 Halted 0 ms 0 KB -