oj.uz

Submission #653127

# Submission time Handle Problem Language Result Execution time Memory
653127 2022-10-25T19:03:27 Z beaconmc Factories (JOI14_factories) C++14
15 / 100
 8000 ms 143432 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[2097152];

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 += 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.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 60 ms 32932 KB Output is correct
2 Correct 2645 ms 41344 KB Output is correct
3 Correct 3823 ms 41272 KB Output is correct
4 Correct 3781 ms 41696 KB Output is correct
5 Correct 4382 ms 41736 KB Output is correct
6 Correct 696 ms 41208 KB Output is correct
7 Correct 3724 ms 41288 KB Output is correct
8 Correct 3952 ms 41292 KB Output is correct
9 Correct 4390 ms 41784 KB Output is correct
10 Correct 680 ms 41260 KB Output is correct
11 Correct 3728 ms 41340 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 32724 KB Output is correct
2 Correct 5526 ms 117184 KB Output is correct
3 Correct 7392 ms 119396 KB Output is correct
4 Correct 1177 ms 114620 KB Output is correct
5 Execution timed out 8061 ms 143432 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 32932 KB Output is correct
2 Correct 2645 ms 41344 KB Output is correct
3 Correct 3823 ms 41272 KB Output is correct
4 Correct 3781 ms 41696 KB Output is correct
5 Correct 4382 ms 41736 KB Output is correct
6 Correct 696 ms 41208 KB Output is correct
7 Correct 3724 ms 41288 KB Output is correct
8 Correct 3952 ms 41292 KB Output is correct
9 Correct 4390 ms 41784 KB Output is correct
10 Correct 680 ms 41260 KB Output is correct
11 Correct 3728 ms 41340 KB Output is correct
12 Correct 23 ms 32724 KB Output is correct
13 Correct 5526 ms 117184 KB Output is correct
14 Correct 7392 ms 119396 KB Output is correct
15 Correct 1177 ms 114620 KB Output is correct
16 Execution timed out 8061 ms 143432 KB Time limit exceeded
17 Halted 0 ms 0 KB -