oj.uz

Submission #656689

# Submission time Handle Problem Language Result Execution time Memory
656689 2022-11-08T03:51:09 Z Hiennoob123 Factories (JOI14_factories) C++14
100 / 100
 4528 ms 293216 KB 
#include<bits/stdc++.h>
#include "factories.h"
#define ll long long
#define ld long double
#define cd complex<ld>
#define pll pair<ll,ll>
#define pii pair<int,int>
#define pld pair<ld,ld>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std ;
ll n ;
ll num = 700 ;
vector<pair<int , ll>> T[500005]  ;
vector<ll> Tc[500005] ;
int depth[500005] ;
ll dis[500005] ;
int lg2[1000005] ;
int Left[500005] ;
bool check[500005] ;
ll sz[500005] ;
ll pa[500005] ;
vector<int> euler ;
vector<pair<int , int>> sparse[20] ;
void build()
{
    for(int i = 0 ; i< 20 ; i++)
    {
        if((1<<i)>euler.size()) break ;
        if(i==0)
        {
            sparse[0].assign(euler.size() , {0 , 0}) ;
            for(int j = 0 ; j< euler.size() ; j++)
            {
                sparse[0][j] = {depth[euler[j]], euler[j]} ;
            }
        }
        else
        {
            sparse[i].assign(euler.size()+1-(1<<i) , {0 , 0}) ;
            for(int j = 0 ; j< euler.size()-(1<<i)+1 ; j++)
            {
                sparse[i][j] = min(sparse[i-1][j] , sparse[i-1][j+(1<<(i-1))]) ;
            }
        }
    }
}
ll LCA(ll u , ll v)
{
    u = Left[u] , v = Left[v] ;
    if(u>v) swap(u , v) ;
    int k = lg2[v-u+1] ;
    pair<int , ll> x = min(sparse[k][u] , sparse[k][v-(1<<k)+1]) ;
    return x.se ;
}
ll distance(ll u , ll v)
{
    int k = LCA(u , v) ;
    return dis[u]+dis[v]-2*dis[k] ;
}
void dfs(ll v , ll par)
{
    Left[v] = euler.size() ;
    euler.push_back(v) ;
    for(int i = 0 ; i< T[v].size() ; i++)
    {
        if(T[v][i].fi==par) continue ;
        dis[T[v][i].fi] = T[v][i].se+dis[v] ;
        depth[T[v][i].fi] = depth[v]+1 ;
        dfs(T[v][i].fi , v) ;
        euler.push_back(v) ;
    }
}
ll dfs_cnt(ll v , ll par)
{
    sz[v] = 1 ;
    for(int i = 0 ; i< T[v].size() ; i++)
    {
        if(T[v][i].fi==par||check[T[v][i].fi]) continue ;
        sz[v] += dfs_cnt(T[v][i].fi , v) ;
    }
    return sz[v] ;
}
ll getcent(ll v , ll par , ll siz)
{
    for(int i = 0 ; i< T[v].size() ; i++)
    {
        if(T[v][i].fi==par||check[T[v][i].fi]) continue ;
        if(sz[T[v][i].fi]*2>=siz) return getcent(T[v][i].fi , v , siz) ;
    }
    return v ;
}
void centroid(ll v , ll par)
{
    ll k = getcent(v , -1 , dfs_cnt(v , -1)) ;
    //cout << k << " " << par << "\n" ;
    pa[k] = par ;
    if(par!=-1)
    {
        Tc[par].push_back(v) ;
    }
    check[k] = 1 ;
    for(int i = 0; i< T[k].size() ; i++)
    {
        if(check[T[k][i].fi]) continue ;
        centroid(T[k][i].fi , k) ;
    }
}
ll val[500005] = {} ;
void Init(int N, int A[], int B[], int D[])
{
    n = N ;
    num = n ;
    for(int i = 0 ; i< n-1 ; i++)
    {
        T[A[i]].push_back(mp(B[i] , D[i])) ;
        T[B[i]].push_back(mp(A[i] , D[i])) ;
    }
    for(int i = 2 ; i<= 1000000 ; i++) lg2[i] = lg2[i/2]+1 ;
    dfs(0 , -1);
    build() ;
    centroid(0 , -1) ;
    for(int i = 0; i<= n;  i++) val[i] = LLONG_MAX ;
}
ll Query(int N, int X[], int M, int Y[])
{
    //cout << -1 ;
    for(int i = 0 ; i< N ; i++)
    {
        ll cur = X[i] ;
        while(cur!=-1)
        {
            //cout << cur << "\n" ;
            val[cur] = min(val[cur] , dis[cur]+dis[X[i]]-2*dis[LCA(cur , X[i])] );
            cur = pa[cur] ;
        }
    }
    ll ans = LLONG_MAX ;
    for(int i = 0; i < M ; i++)
    {
        ll cur = Y[i] ;
        while(cur!=-1)
        {
            //cout << cur << "\n" ;
            if(val[cur]!=LLONG_MAX) ans = min(ans , val[cur]+dis[cur]+dis[Y[i]]-2*dis[LCA(cur , Y[i])]) ;
            cur = pa[cur] ;
        }
    }
    for(int i = 0 ; i< N ; i++)
    {
        ll cur = X[i] ;
        while(cur!=-1)
        {
            val[cur] = LLONG_MAX ;
            cur = pa[cur] ;
        }
    }
    return ans;
}

Compilation message

factories.cpp: In function 'void build()':
factories.cpp:31:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |         if((1<<i)>euler.size()) break ;
      |            ~~~~~~^~~~~~~~~~~~~
factories.cpp:35:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |             for(int j = 0 ; j< euler.size() ; j++)
      |                             ~^~~~~~~~~~~~~~
factories.cpp:43:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |             for(int j = 0 ; j< euler.size()-(1<<i)+1 ; j++)
      |                             ~^~~~~~~~~~~~~~~~~~~~~~~
factories.cpp: In function 'void dfs(long long int, long long int)':
factories.cpp:67:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for(int i = 0 ; i< T[v].size() ; i++)
      |                     ~^~~~~~~~~~~~~
factories.cpp: In function 'long long int dfs_cnt(long long int, long long int)':
factories.cpp:79:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for(int i = 0 ; i< T[v].size() ; i++)
      |                     ~^~~~~~~~~~~~~
factories.cpp: In function 'long long int getcent(long long int, long long int, long long int)':
factories.cpp:88:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     for(int i = 0 ; i< T[v].size() ; i++)
      |                     ~^~~~~~~~~~~~~
factories.cpp: In function 'void centroid(long long int, long long int)':
factories.cpp:105:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |     for(int i = 0; i< T[k].size() ; i++)
      |                    ~^~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 28168 KB Output is correct
2 Correct 375 ms 37352 KB Output is correct
3 Correct 502 ms 37464 KB Output is correct
4 Correct 427 ms 37324 KB Output is correct
5 Correct 479 ms 37876 KB Output is correct
6 Correct 198 ms 37324 KB Output is correct
7 Correct 485 ms 37416 KB Output is correct
8 Correct 512 ms 37488 KB Output is correct
9 Correct 509 ms 37880 KB Output is correct
10 Correct 224 ms 37328 KB Output is correct
11 Correct 489 ms 37400 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 28000 KB Output is correct
2 Correct 1841 ms 247032 KB Output is correct
3 Correct 2532 ms 251708 KB Output is correct
4 Correct 708 ms 244368 KB Output is correct
5 Correct 3072 ms 293216 KB Output is correct
6 Correct 2574 ms 252888 KB Output is correct
7 Correct 1262 ms 77084 KB Output is correct
8 Correct 349 ms 76872 KB Output is correct
9 Correct 1254 ms 83220 KB Output is correct
10 Correct 1215 ms 78356 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 28168 KB Output is correct
2 Correct 375 ms 37352 KB Output is correct
3 Correct 502 ms 37464 KB Output is correct
4 Correct 427 ms 37324 KB Output is correct
5 Correct 479 ms 37876 KB Output is correct
6 Correct 198 ms 37324 KB Output is correct
7 Correct 485 ms 37416 KB Output is correct
8 Correct 512 ms 37488 KB Output is correct
9 Correct 509 ms 37880 KB Output is correct
10 Correct 224 ms 37328 KB Output is correct
11 Correct 489 ms 37400 KB Output is correct
12 Correct 16 ms 28000 KB Output is correct
13 Correct 1841 ms 247032 KB Output is correct
14 Correct 2532 ms 251708 KB Output is correct
15 Correct 708 ms 244368 KB Output is correct
16 Correct 3072 ms 293216 KB Output is correct
17 Correct 2574 ms 252888 KB Output is correct
18 Correct 1262 ms 77084 KB Output is correct
19 Correct 349 ms 76872 KB Output is correct
20 Correct 1254 ms 83220 KB Output is correct
21 Correct 1215 ms 78356 KB Output is correct
22 Correct 2707 ms 248724 KB Output is correct
23 Correct 2494 ms 251128 KB Output is correct
24 Correct 3961 ms 253064 KB Output is correct
25 Correct 3940 ms 256832 KB Output is correct
26 Correct 3871 ms 253524 KB Output is correct
27 Correct 4528 ms 287176 KB Output is correct
28 Correct 933 ms 248392 KB Output is correct
29 Correct 3801 ms 253028 KB Output is correct
30 Correct 3728 ms 252092 KB Output is correct
31 Correct 3715 ms 253384 KB Output is correct
32 Correct 1515 ms 88900 KB Output is correct
33 Correct 368 ms 81720 KB Output is correct
34 Correct 1025 ms 78668 KB Output is correct
35 Correct 1125 ms 78640 KB Output is correct
36 Correct 1327 ms 79688 KB Output is correct
37 Correct 1548 ms 79860 KB Output is correct