oj.uz

Submission #656599

# Submission time Handle Problem Language Result Execution time Memory
656599 2022-11-08T02:17:16 Z Hiennoob123 Factories (JOI14_factories) C++14
33 / 100
 8000 ms 409284 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 ;
    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)
{
    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" ;
    //cout << num ;
    if(N*M>n*5)
    {
        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:114: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]
  114 |             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 20456 KB Output is correct
2 Correct 914 ms 30820 KB Output is correct
3 Correct 2627 ms 30848 KB Output is correct
4 Correct 480 ms 31100 KB Output is correct
5 Correct 801 ms 31348 KB Output is correct
6 Correct 825 ms 31192 KB Output is correct
7 Correct 2693 ms 30876 KB Output is correct
8 Correct 431 ms 31008 KB Output is correct
9 Correct 798 ms 31420 KB Output is correct
10 Correct 846 ms 31148 KB Output is correct
11 Correct 2721 ms 30888 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 996 ms 374964 KB Output is correct
3 Correct 1104 ms 378848 KB Output is correct
4 Correct 785 ms 372624 KB Output is correct
5 Correct 1020 ms 409284 KB Output is correct
6 Correct 981 ms 380040 KB Output is correct
7 Correct 922 ms 93240 KB Output is correct
8 Correct 636 ms 92728 KB Output is correct
9 Correct 654 ms 97656 KB Output is correct
10 Correct 724 ms 94380 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 20456 KB Output is correct
2 Correct 914 ms 30820 KB Output is correct
3 Correct 2627 ms 30848 KB Output is correct
4 Correct 480 ms 31100 KB Output is correct
5 Correct 801 ms 31348 KB Output is correct
6 Correct 825 ms 31192 KB Output is correct
7 Correct 2693 ms 30876 KB Output is correct
8 Correct 431 ms 31008 KB Output is correct
9 Correct 798 ms 31420 KB Output is correct
10 Correct 846 ms 31148 KB Output is correct
11 Correct 2721 ms 30888 KB Output is correct
12 Correct 12 ms 20180 KB Output is correct
13 Correct 996 ms 374964 KB Output is correct
14 Correct 1104 ms 378848 KB Output is correct
15 Correct 785 ms 372624 KB Output is correct
16 Correct 1020 ms 409284 KB Output is correct
17 Correct 981 ms 380040 KB Output is correct
18 Correct 922 ms 93240 KB Output is correct
19 Correct 636 ms 92728 KB Output is correct
20 Correct 654 ms 97656 KB Output is correct
21 Correct 724 ms 94380 KB Output is correct
22 Execution timed out 8053 ms 384524 KB Time limit exceeded
23 Halted 0 ms 0 KB -