oj.uz

Submission #656614

# Submission time Handle Problem Language Result Execution time Memory
656614 2022-11-08T02:30:11 Z Hiennoob123 Factories (JOI14_factories) C++17
33 / 100
 8000 ms 262536 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]  ;
int depth[500005] ;
ll dis[500005] ;
int lg2[1000005] ;
int Left[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 ;
}
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 ;
    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() ;
}
ll distance(ll u , ll v)
{
    int 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" ;
    //cout << num ;
    if(N*M>500000)
    {
        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<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<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<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<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:114:30: 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]
  114 |             for(int i = 0 ; i< T[x].size() ; i++)
      |                             ~^~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 16340 KB Output is correct
2 Correct 2597 ms 25492 KB Output is correct
3 Correct 3124 ms 25500 KB Output is correct
4 Correct 1108 ms 25608 KB Output is correct
5 Correct 1813 ms 26084 KB Output is correct
6 Correct 1711 ms 25700 KB Output is correct
7 Correct 2733 ms 25396 KB Output is correct
8 Correct 999 ms 25464 KB Output is correct
9 Correct 1777 ms 25980 KB Output is correct
10 Correct 1740 ms 25676 KB Output is correct
11 Correct 2735 ms 25408 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 16212 KB Output is correct
2 Correct 859 ms 214600 KB Output is correct
3 Correct 904 ms 220336 KB Output is correct
4 Correct 660 ms 212760 KB Output is correct
5 Correct 884 ms 262536 KB Output is correct
6 Correct 896 ms 221452 KB Output is correct
7 Correct 774 ms 61632 KB Output is correct
8 Correct 509 ms 61108 KB Output is correct
9 Correct 521 ms 67420 KB Output is correct
10 Correct 598 ms 62632 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 16340 KB Output is correct
2 Correct 2597 ms 25492 KB Output is correct
3 Correct 3124 ms 25500 KB Output is correct
4 Correct 1108 ms 25608 KB Output is correct
5 Correct 1813 ms 26084 KB Output is correct
6 Correct 1711 ms 25700 KB Output is correct
7 Correct 2733 ms 25396 KB Output is correct
8 Correct 999 ms 25464 KB Output is correct
9 Correct 1777 ms 25980 KB Output is correct
10 Correct 1740 ms 25676 KB Output is correct
11 Correct 2735 ms 25408 KB Output is correct
12 Correct 10 ms 16212 KB Output is correct
13 Correct 859 ms 214600 KB Output is correct
14 Correct 904 ms 220336 KB Output is correct
15 Correct 660 ms 212760 KB Output is correct
16 Correct 884 ms 262536 KB Output is correct
17 Correct 896 ms 221452 KB Output is correct
18 Correct 774 ms 61632 KB Output is correct
19 Correct 509 ms 61108 KB Output is correct
20 Correct 521 ms 67420 KB Output is correct
21 Correct 598 ms 62632 KB Output is correct
22 Execution timed out 8044 ms 224240 KB Time limit exceeded
23 Halted 0 ms 0 KB -