oj.uz

Submission #653219

# Submission time Handle Problem Language Result Execution time Memory
653219 2022-10-26T08:55:24 Z beaconmc Factories (JOI14_factories) C++14
33 / 100
 8000 ms 126300 KB 
#pragma GCC optimize ("Ofast")

#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 28756 KB Output is correct
2 Correct 1125 ms 37220 KB Output is correct
3 Correct 1709 ms 37404 KB Output is correct
4 Correct 1639 ms 37592 KB Output is correct
5 Correct 1527 ms 37652 KB Output is correct
6 Correct 307 ms 37068 KB Output is correct
7 Correct 1664 ms 37296 KB Output is correct
8 Correct 1722 ms 37304 KB Output is correct
9 Correct 1578 ms 37732 KB Output is correct
10 Correct 309 ms 37208 KB Output is correct
11 Correct 1641 ms 37288 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 3067 ms 90816 KB Output is correct
3 Correct 4485 ms 93772 KB Output is correct
4 Correct 729 ms 88332 KB Output is correct
5 Correct 5041 ms 118164 KB Output is correct
6 Correct 4835 ms 94972 KB Output is correct
7 Correct 3867 ms 49624 KB Output is correct
8 Correct 469 ms 49512 KB Output is correct
9 Correct 3615 ms 53468 KB Output is correct
10 Correct 4062 ms 50928 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 28756 KB Output is correct
2 Correct 1125 ms 37220 KB Output is correct
3 Correct 1709 ms 37404 KB Output is correct
4 Correct 1639 ms 37592 KB Output is correct
5 Correct 1527 ms 37652 KB Output is correct
6 Correct 307 ms 37068 KB Output is correct
7 Correct 1664 ms 37296 KB Output is correct
8 Correct 1722 ms 37304 KB Output is correct
9 Correct 1578 ms 37732 KB Output is correct
10 Correct 309 ms 37208 KB Output is correct
11 Correct 1641 ms 37288 KB Output is correct
12 Correct 18 ms 28628 KB Output is correct
13 Correct 3067 ms 90816 KB Output is correct
14 Correct 4485 ms 93772 KB Output is correct
15 Correct 729 ms 88332 KB Output is correct
16 Correct 5041 ms 118164 KB Output is correct
17 Correct 4835 ms 94972 KB Output is correct
18 Correct 3867 ms 49624 KB Output is correct
19 Correct 469 ms 49512 KB Output is correct
20 Correct 3615 ms 53468 KB Output is correct
21 Correct 4062 ms 50928 KB Output is correct
22 Correct 4729 ms 99812 KB Output is correct
23 Correct 5872 ms 104728 KB Output is correct
24 Correct 7636 ms 107572 KB Output is correct
25 Correct 7531 ms 108968 KB Output is correct
26 Correct 7693 ms 95800 KB Output is correct
27 Correct 7457 ms 126300 KB Output is correct
28 Correct 1091 ms 118668 KB Output is correct
29 Execution timed out 8096 ms 119624 KB Time limit exceeded
30 Halted 0 ms 0 KB -