oj.uz

Submission #656587

# Submission time Handle Problem Language Result Execution time Memory
656587 2022-11-08T02:09:53 Z Hiennoob123 Factories (JOI14_factories) C++14
33 / 100
 8000 ms 409164 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 = 3000 ;
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 27 ms 20308 KB Output is correct
2 Correct 917 ms 30440 KB Output is correct
3 Correct 2605 ms 30704 KB Output is correct
4 Correct 483 ms 30920 KB Output is correct
5 Correct 815 ms 31192 KB Output is correct
6 Correct 839 ms 31036 KB Output is correct
7 Correct 2722 ms 30804 KB Output is correct
8 Correct 418 ms 30820 KB Output is correct
9 Correct 800 ms 31072 KB Output is correct
10 Correct 828 ms 30900 KB Output is correct
11 Correct 2567 ms 30924 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 20180 KB Output is correct
2 Correct 1010 ms 374908 KB Output is correct
3 Correct 1039 ms 378856 KB Output is correct
4 Correct 780 ms 372464 KB Output is correct
5 Correct 1008 ms 409164 KB Output is correct
6 Correct 972 ms 379908 KB Output is correct
7 Correct 937 ms 92904 KB Output is correct
8 Correct 644 ms 92352 KB Output is correct
9 Correct 649 ms 97348 KB Output is correct
10 Correct 696 ms 93980 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 20308 KB Output is correct
2 Correct 917 ms 30440 KB Output is correct
3 Correct 2605 ms 30704 KB Output is correct
4 Correct 483 ms 30920 KB Output is correct
5 Correct 815 ms 31192 KB Output is correct
6 Correct 839 ms 31036 KB Output is correct
7 Correct 2722 ms 30804 KB Output is correct
8 Correct 418 ms 30820 KB Output is correct
9 Correct 800 ms 31072 KB Output is correct
10 Correct 828 ms 30900 KB Output is correct
11 Correct 2567 ms 30924 KB Output is correct
12 Correct 12 ms 20180 KB Output is correct
13 Correct 1010 ms 374908 KB Output is correct
14 Correct 1039 ms 378856 KB Output is correct
15 Correct 780 ms 372464 KB Output is correct
16 Correct 1008 ms 409164 KB Output is correct
17 Correct 972 ms 379908 KB Output is correct
18 Correct 937 ms 92904 KB Output is correct
19 Correct 644 ms 92352 KB Output is correct
20 Correct 649 ms 97348 KB Output is correct
21 Correct 696 ms 93980 KB Output is correct
22 Execution timed out 8092 ms 384676 KB Time limit exceeded
23 Halted 0 ms 0 KB -