oj.uz

Submission #653131

# Submission time Handle Problem Language Result Execution time Memory
653131 2022-10-25T19:08:03 Z beaconmc Factories (JOI14_factories) C++14
15 / 100
 8000 ms 124852 KB 
#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: In function 'void Init(int, int*, int*, int*)':
factories.cpp:7: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]
    7 | #define FOR(i,x,y) for(ll i=x; i<y; i++)
......
  164 |   FOR(i,0,euler.size()){
      |       ~~~~~~~~~~~~~~~~           
factories.cpp:164:3: note: in expansion of macro 'FOR'
  164 |   FOR(i,0,euler.size()){
      |   ^~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 32852 KB Output is correct
2 Correct 2408 ms 41348 KB Output is correct
3 Correct 3428 ms 41488 KB Output is correct
4 Correct 3496 ms 41792 KB Output is correct
5 Correct 4074 ms 41836 KB Output is correct
6 Correct 608 ms 41340 KB Output is correct
7 Correct 3547 ms 41300 KB Output is correct
8 Correct 3745 ms 41300 KB Output is correct
9 Correct 4073 ms 41788 KB Output is correct
10 Correct 598 ms 41240 KB Output is correct
11 Correct 3502 ms 41280 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 32712 KB Output is correct
2 Correct 4863 ms 98536 KB Output is correct
3 Correct 7064 ms 101500 KB Output is correct
4 Correct 1103 ms 96276 KB Output is correct
5 Execution timed out 8071 ms 124852 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 32852 KB Output is correct
2 Correct 2408 ms 41348 KB Output is correct
3 Correct 3428 ms 41488 KB Output is correct
4 Correct 3496 ms 41792 KB Output is correct
5 Correct 4074 ms 41836 KB Output is correct
6 Correct 608 ms 41340 KB Output is correct
7 Correct 3547 ms 41300 KB Output is correct
8 Correct 3745 ms 41300 KB Output is correct
9 Correct 4073 ms 41788 KB Output is correct
10 Correct 598 ms 41240 KB Output is correct
11 Correct 3502 ms 41280 KB Output is correct
12 Correct 20 ms 32712 KB Output is correct
13 Correct 4863 ms 98536 KB Output is correct
14 Correct 7064 ms 101500 KB Output is correct
15 Correct 1103 ms 96276 KB Output is correct
16 Execution timed out 8071 ms 124852 KB Time limit exceeded
17 Halted 0 ms 0 KB -