oj.uz

Submission #656621

# Submission time Handle Problem Language Result Execution time Memory
656621 2022-11-08T02:38:17 Z Hiennoob123 Factories (JOI14_factories) C++17
33 / 100
 8000 ms 262472 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>n)
    {
        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 , dis[X[i]]+dis[Y[j]]-2*dis[LCA(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 30 ms 16340 KB Output is correct
2 Correct 886 ms 25440 KB Output is correct
3 Correct 2600 ms 25728 KB Output is correct
4 Correct 465 ms 25608 KB Output is correct
5 Correct 799 ms 25968 KB Output is correct
6 Correct 818 ms 25588 KB Output is correct
7 Correct 2546 ms 25600 KB Output is correct
8 Correct 424 ms 25500 KB Output is correct
9 Correct 804 ms 26060 KB Output is correct
10 Correct 820 ms 25724 KB Output is correct
11 Correct 2552 ms 25452 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16172 KB Output is correct
2 Correct 842 ms 214608 KB Output is correct
3 Correct 896 ms 220396 KB Output is correct
4 Correct 651 ms 212644 KB Output is correct
5 Correct 861 ms 262472 KB Output is correct
6 Correct 850 ms 221440 KB Output is correct
7 Correct 796 ms 61504 KB Output is correct
8 Correct 494 ms 61056 KB Output is correct
9 Correct 537 ms 67296 KB Output is correct
10 Correct 580 ms 62652 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 16340 KB Output is correct
2 Correct 886 ms 25440 KB Output is correct
3 Correct 2600 ms 25728 KB Output is correct
4 Correct 465 ms 25608 KB Output is correct
5 Correct 799 ms 25968 KB Output is correct
6 Correct 818 ms 25588 KB Output is correct
7 Correct 2546 ms 25600 KB Output is correct
8 Correct 424 ms 25500 KB Output is correct
9 Correct 804 ms 26060 KB Output is correct
10 Correct 820 ms 25724 KB Output is correct
11 Correct 2552 ms 25452 KB Output is correct
12 Correct 9 ms 16172 KB Output is correct
13 Correct 842 ms 214608 KB Output is correct
14 Correct 896 ms 220396 KB Output is correct
15 Correct 651 ms 212644 KB Output is correct
16 Correct 861 ms 262472 KB Output is correct
17 Correct 850 ms 221440 KB Output is correct
18 Correct 796 ms 61504 KB Output is correct
19 Correct 494 ms 61056 KB Output is correct
20 Correct 537 ms 67296 KB Output is correct
21 Correct 580 ms 62652 KB Output is correct
22 Execution timed out 8084 ms 224252 KB Time limit exceeded
23 Halted 0 ms 0 KB -