oj.uz

Submission #656589

# Submission time Handle Problem Language Result Execution time Memory
656589 2022-11-08T02:11:08 Z Hiennoob123 Factories (JOI14_factories) C++14
33 / 100
 8000 ms 409356 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<pll> T[500005]  ;
ll depth[500005] ;
ll dis[500005] ;
ll lg2[1000005] ;
ll Left[500005] ;
vector<ll> euler ;
vector<pll> 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) ;
    ll k = lg2[v-u+1] ;
    pll x = min(sparse[k][u] , sparse[k][v-(1<<k)+1]) ;
    return x.se ;
}
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) ;
    }
}
void Init(int N, int A[], int B[], int D[])
{
    n = 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() ;
}
ll distance(ll u , ll v)
{
    ll k = LCA(u , v) ;
    //cout << u << " " << v << " " << k << "\n" ;
    //cout << dis[u]+dis[v]-2*dis[k] << "\n" ;
    return dis[u]+dis[v]-2*dis[k] ;
}
ll dist[500005] = {} ;
bool check[500005] = {} ;
ll Query(int N, int X[], int M, int Y[])
{
    //cout<< N << " " << M << "\n" ;
    if(N*M>num)
    {
        for(int i = 0 ; i<= n ; i++)
        {
            dist[i] = LLONG_MAX ;
            check[i] = 0 ;
        }
        priority_queue<pll , vector<pll> , greater<pll>> q ;
        for(int i = 0 ; i< N ;i++)
        {
            dist[X[i]] = 0 ;
            q.push(mp(0 , X[i])) ;
        }
        while(!q.empty())
        {
            ll le = q.top().fi , x = q.top().se;
            q.pop() ;
            //cout << le << " " << x << "\n" ;
            if(le!=dist[x]||check[x]) continue ;
            check[x] = 1 ;
            //cout << T[x][0].fi << "\n" ;
            for(int i = 0 ; i< T[x].size() ; i++)
            {
                if(dist[T[x][i].fi]>T[x][i].se+le)
                {
                    dist[T[x][i].fi] = T[x][i].se+le ;
                    q.push(mp(dist[T[x][i].fi] , T[x][i].fi)) ;
                }
            }
        }
        ll ans = LLONG_MAX ;
        for(int i = 0 ; i< M ; i++)
        {
            ans = min(ans , dist[Y[i]]) ;
        }
        return ans ;
    }
    else
    {
        ll ans = LLONG_MAX ;
        for(int i = 0 ; i< N ; i++)
        {
            for(int j = 0 ; j< M ; j++)
            {
                ans = min(ans , distance(X[i] , Y[j])) ;
            }
        }
        return ans ;
    }
    return 0;
}

Compilation message

factories.cpp: In function 'void build()':
factories.cpp:27:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |         if((1<<i)>euler.size()) break ;
      |            ~~~~~~^~~~~~~~~~~~~
factories.cpp:31:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |             for(int j = 0 ; j< euler.size() ; j++)
      |                             ~^~~~~~~~~~~~~~
factories.cpp:39:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |             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:58:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for(int i = 0 ; i< T[v].size() ; i++)
      |                     ~^~~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:112:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |             for(int i = 0 ; i< T[x].size() ; i++)
      |                             ~^~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 20308 KB Output is correct
2 Correct 906 ms 30432 KB Output is correct
3 Correct 2750 ms 30452 KB Output is correct
4 Correct 868 ms 30592 KB Output is correct
5 Correct 833 ms 30820 KB Output is correct
6 Correct 1014 ms 30800 KB Output is correct
7 Correct 2765 ms 30456 KB Output is correct
8 Correct 873 ms 30540 KB Output is correct
9 Correct 797 ms 30928 KB Output is correct
10 Correct 838 ms 30852 KB Output is correct
11 Correct 2572 ms 30752 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 20180 KB Output is correct
2 Correct 990 ms 374820 KB Output is correct
3 Correct 1054 ms 378796 KB Output is correct
4 Correct 768 ms 372444 KB Output is correct
5 Correct 1008 ms 409356 KB Output is correct
6 Correct 1004 ms 379928 KB Output is correct
7 Correct 964 ms 93796 KB Output is correct
8 Correct 672 ms 93740 KB Output is correct
9 Correct 668 ms 98444 KB Output is correct
10 Correct 702 ms 95160 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 20308 KB Output is correct
2 Correct 906 ms 30432 KB Output is correct
3 Correct 2750 ms 30452 KB Output is correct
4 Correct 868 ms 30592 KB Output is correct
5 Correct 833 ms 30820 KB Output is correct
6 Correct 1014 ms 30800 KB Output is correct
7 Correct 2765 ms 30456 KB Output is correct
8 Correct 873 ms 30540 KB Output is correct
9 Correct 797 ms 30928 KB Output is correct
10 Correct 838 ms 30852 KB Output is correct
11 Correct 2572 ms 30752 KB Output is correct
12 Correct 11 ms 20180 KB Output is correct
13 Correct 990 ms 374820 KB Output is correct
14 Correct 1054 ms 378796 KB Output is correct
15 Correct 768 ms 372444 KB Output is correct
16 Correct 1008 ms 409356 KB Output is correct
17 Correct 1004 ms 379928 KB Output is correct
18 Correct 964 ms 93796 KB Output is correct
19 Correct 672 ms 93740 KB Output is correct
20 Correct 668 ms 98444 KB Output is correct
21 Correct 702 ms 95160 KB Output is correct
22 Execution timed out 8023 ms 384724 KB Time limit exceeded
23 Halted 0 ms 0 KB -