oj.uz

Submission #656604

# Submission time Handle Problem Language Result Execution time Memory
656604 2022-11-08T02:20:12 Z Hiennoob123 Factories (JOI14_factories) C++14
33 / 100
 8000 ms 409112 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/10)
    {
        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 37 ms 20308 KB Output is correct
2 Correct 898 ms 30560 KB Output is correct
3 Correct 2599 ms 30604 KB Output is correct
4 Correct 949 ms 30700 KB Output is correct
5 Correct 800 ms 30848 KB Output is correct
6 Correct 833 ms 30632 KB Output is correct
7 Correct 2605 ms 30456 KB Output is correct
8 Correct 1071 ms 30444 KB Output is correct
9 Correct 820 ms 30816 KB Output is correct
10 Correct 906 ms 30612 KB Output is correct
11 Correct 3019 ms 30456 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 20180 KB Output is correct
2 Correct 985 ms 374800 KB Output is correct
3 Correct 1087 ms 378864 KB Output is correct
4 Correct 843 ms 372552 KB Output is correct
5 Correct 1034 ms 409112 KB Output is correct
6 Correct 1505 ms 379828 KB Output is correct
7 Correct 1106 ms 93300 KB Output is correct
8 Correct 688 ms 92916 KB Output is correct
9 Correct 700 ms 97756 KB Output is correct
10 Correct 911 ms 94608 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 20308 KB Output is correct
2 Correct 898 ms 30560 KB Output is correct
3 Correct 2599 ms 30604 KB Output is correct
4 Correct 949 ms 30700 KB Output is correct
5 Correct 800 ms 30848 KB Output is correct
6 Correct 833 ms 30632 KB Output is correct
7 Correct 2605 ms 30456 KB Output is correct
8 Correct 1071 ms 30444 KB Output is correct
9 Correct 820 ms 30816 KB Output is correct
10 Correct 906 ms 30612 KB Output is correct
11 Correct 3019 ms 30456 KB Output is correct
12 Correct 15 ms 20180 KB Output is correct
13 Correct 985 ms 374800 KB Output is correct
14 Correct 1087 ms 378864 KB Output is correct
15 Correct 843 ms 372552 KB Output is correct
16 Correct 1034 ms 409112 KB Output is correct
17 Correct 1505 ms 379828 KB Output is correct
18 Correct 1106 ms 93300 KB Output is correct
19 Correct 688 ms 92916 KB Output is correct
20 Correct 700 ms 97756 KB Output is correct
21 Correct 911 ms 94608 KB Output is correct
22 Execution timed out 8111 ms 384644 KB Time limit exceeded
23 Halted 0 ms 0 KB -