oj.uz

Submission #653132

# Submission time Handle Problem Language Result Execution time Memory
653132 2022-10-25T19:09:30 Z beaconmc Factories (JOI14_factories) C++14
15 / 100
 4381 ms 172252 KB 
#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 tree[1048576];

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;
}



void update(ll a, ll k){
  a += 524288;
  tree[a] = k;
  while (a){
    a/=2;
    if (dists[tree[2*a]]==dists[tree[2*a+1]] && dists[tree[2*a+1]]==1000000000000000) tree[a] = 0;
    else tree[a] = dists[tree[2*a]] < dists[tree[2*a+1]] ? tree[2*a] : tree[2*a+1];
  }
}

ll query(ll a, ll b, ll k=1, ll x=0, ll y = 524288-1){
  //cout << a<<" "<<b<<" "<<x << " " << y << " "<<k<< endl;

  if (b<x || a>y) return 0;
  if (a<=x && y<=b){
    return tree[k];
  }
  ll d = (x+y)/2;

  ll sus = query(a,b,2*k,x,d);
  ll sussy = query(a,b,2*k+1,d+1,y);

  if (dists[sus] < dists[sussy]) return sus;
  return sussy;


}





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) tree[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()){
    update(i, euler[i]);
  }



  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:5: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]
    5 | #define FOR(i,x,y) for(ll i=x; i<y; i++)
......
  162 |   FOR(i,0,euler.size()){
      |       ~~~~~~~~~~~~~~~~           
factories.cpp:162:3: note: in expansion of macro 'FOR'
  162 |   FOR(i,0,euler.size()){
      |   ^~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 32972 KB Output is correct
2 Correct 2517 ms 41256 KB Output is correct
3 Correct 3704 ms 41544 KB Output is correct
4 Correct 3666 ms 41680 KB Output is correct
5 Correct 4279 ms 41884 KB Output is correct
6 Correct 670 ms 41152 KB Output is correct
7 Correct 3687 ms 41452 KB Output is correct
8 Correct 3896 ms 41480 KB Output is correct
9 Correct 4381 ms 41804 KB Output is correct
10 Correct 663 ms 41292 KB Output is correct
11 Correct 3758 ms 41392 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 32724 KB Output is correct
2 Runtime error 754 ms 172252 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 58 ms 32972 KB Output is correct
2 Correct 2517 ms 41256 KB Output is correct
3 Correct 3704 ms 41544 KB Output is correct
4 Correct 3666 ms 41680 KB Output is correct
5 Correct 4279 ms 41884 KB Output is correct
6 Correct 670 ms 41152 KB Output is correct
7 Correct 3687 ms 41452 KB Output is correct
8 Correct 3896 ms 41480 KB Output is correct
9 Correct 4381 ms 41804 KB Output is correct
10 Correct 663 ms 41292 KB Output is correct
11 Correct 3758 ms 41392 KB Output is correct
12 Correct 27 ms 32724 KB Output is correct
13 Runtime error 754 ms 172252 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -