oj.uz

Submission #653135

# Submission time Handle Problem Language Result Execution time Memory
653135 2022-10-25T19:17:24 Z beaconmc Factories (JOI14_factories) C++11
15 / 100
 8000 ms 124996 KB 
#pragma gcc optimize ( unroll-loops )
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
#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:1: warning: ignoring '#pragma gcc optimize' [-Wunknown-pragmas]
    1 | #pragma gcc optimize ( unroll-loops )
      | 
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++)
......
  165 |   FOR(i,0,euler.size()){
      |       ~~~~~~~~~~~~~~~~           
factories.cpp:165:3: note: in expansion of macro 'FOR'
  165 |   FOR(i,0,euler.size()){
      |   ^~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 32932 KB Output is correct
2 Correct 2314 ms 41320 KB Output is correct
3 Correct 3371 ms 41660 KB Output is correct
4 Correct 3363 ms 41852 KB Output is correct
5 Correct 3854 ms 41836 KB Output is correct
6 Correct 597 ms 41296 KB Output is correct
7 Correct 3295 ms 41492 KB Output is correct
8 Correct 3500 ms 41448 KB Output is correct
9 Correct 3879 ms 41804 KB Output is correct
10 Correct 606 ms 41256 KB Output is correct
11 Correct 3597 ms 41412 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 32784 KB Output is correct
2 Correct 5393 ms 98548 KB Output is correct
3 Correct 7069 ms 101436 KB Output is correct
4 Correct 1153 ms 96448 KB Output is correct
5 Execution timed out 8042 ms 124996 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 32932 KB Output is correct
2 Correct 2314 ms 41320 KB Output is correct
3 Correct 3371 ms 41660 KB Output is correct
4 Correct 3363 ms 41852 KB Output is correct
5 Correct 3854 ms 41836 KB Output is correct
6 Correct 597 ms 41296 KB Output is correct
7 Correct 3295 ms 41492 KB Output is correct
8 Correct 3500 ms 41448 KB Output is correct
9 Correct 3879 ms 41804 KB Output is correct
10 Correct 606 ms 41256 KB Output is correct
11 Correct 3597 ms 41412 KB Output is correct
12 Correct 22 ms 32784 KB Output is correct
13 Correct 5393 ms 98548 KB Output is correct
14 Correct 7069 ms 101436 KB Output is correct
15 Correct 1153 ms 96448 KB Output is correct
16 Execution timed out 8042 ms 124996 KB Time limit exceeded
17 Halted 0 ms 0 KB -