oj.uz

Submission #653148

# Submission time Handle Problem Language Result Execution time Memory
653148 2022-10-25T20:01:37 Z beaconmc Factories (JOI14_factories) C++14
0 / 100
 18 ms 32852 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){
  dists[a] = v;
  euler.push_back(a);
  for (auto&i : edges[a]){
    if (i.first!=p){ 
      euler.push_back(a);
      dfs2(i.first, a, v+i.second);
      
    }
    
  }
  
}




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]) tree[k] = sus;
  else tree[k] = sussy;
  return tree[k];


}





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(make_pair(b,c));
    edges[b].push_back(make_pair(a,c));
  }

  dfs2(1,-1,0);


  FOR(i,0,euler.size()){
    tree[i+1048576] = euler[i];
  }



  decomp(1,-1);


}



long long Query(int S, int X[], int T, int Y[]) {
  return 0;
  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++)
......
  157 |   FOR(i,0,euler.size()){
      |       ~~~~~~~~~~~~~~~~           
factories.cpp:157:3: note: in expansion of macro 'FOR'
  157 |   FOR(i,0,euler.size()){
      |   ^~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 32852 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 32724 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 32852 KB Output isn't correct
2 Halted 0 ms 0 KB -