oj.uz

Submission #653126

# Submission time Handle Problem Language Result Execution time Memory
653126 2022-10-25T19:01:03 Z beaconmc Factories (JOI14_factories) C++14
15 / 100
 6027 ms 524288 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[300000];
vector<vector<ll>> edges[300000];
ll sub[300000], par[300000], ans[300000];
ll n,m,root;

ll tree[2097152];

ll first[300000];
ll dists[300000];
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[0]!=p){ 
      dfs2(i[0], a, v+i[1]);
      euler.push_back(a);
    }
    
  }
  dists[a] = v;
}



void update(ll a, ll k){
  a += 1048576;
  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 = 1048576-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[0]!=p && !r[i[0]]) sub[a] += dfs(i[0], a);
  }
  return sub[a];
}

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

  for (auto&i : edges[a]){
    if (i[0]!=p && !r[i[0]] && sub[i[0]]*2 > sz){
      return centroid(i[0], 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[0]]) decomp(i[0], 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,300000) 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 54 ms 20948 KB Output is correct
2 Correct 3039 ms 39156 KB Output is correct
3 Correct 3778 ms 39348 KB Output is correct
4 Correct 3822 ms 39668 KB Output is correct
5 Correct 4387 ms 39688 KB Output is correct
6 Correct 737 ms 39072 KB Output is correct
7 Correct 3735 ms 39376 KB Output is correct
8 Correct 3954 ms 39236 KB Output is correct
9 Correct 4363 ms 39608 KB Output is correct
10 Correct 704 ms 39036 KB Output is correct
11 Correct 3720 ms 39484 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 20692 KB Output is correct
2 Runtime error 6027 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 20948 KB Output is correct
2 Correct 3039 ms 39156 KB Output is correct
3 Correct 3778 ms 39348 KB Output is correct
4 Correct 3822 ms 39668 KB Output is correct
5 Correct 4387 ms 39688 KB Output is correct
6 Correct 737 ms 39072 KB Output is correct
7 Correct 3735 ms 39376 KB Output is correct
8 Correct 3954 ms 39236 KB Output is correct
9 Correct 4363 ms 39608 KB Output is correct
10 Correct 704 ms 39036 KB Output is correct
11 Correct 3720 ms 39484 KB Output is correct
12 Correct 15 ms 20692 KB Output is correct
13 Runtime error 6027 ms 524288 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -