oj.uz

Submission #656620

# Submission time Handle Problem Language Result Execution time Memory
656620 2022-11-08T02:37:10 Z Hiennoob123 Factories (JOI14_factories) C++17
33 / 100
 8000 ms 262468 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>4*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 26 ms 16340 KB Output is correct
2 Correct 866 ms 25480 KB Output is correct
3 Correct 2616 ms 25456 KB Output is correct
4 Correct 454 ms 25608 KB Output is correct
5 Correct 783 ms 25980 KB Output is correct
6 Correct 797 ms 25588 KB Output is correct
7 Correct 2601 ms 25716 KB Output is correct
8 Correct 418 ms 25476 KB Output is correct
9 Correct 809 ms 25964 KB Output is correct
10 Correct 832 ms 25644 KB Output is correct
11 Correct 2573 ms 25708 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 843 ms 214688 KB Output is correct
3 Correct 902 ms 220400 KB Output is correct
4 Correct 653 ms 212552 KB Output is correct
5 Correct 871 ms 262468 KB Output is correct
6 Correct 867 ms 221420 KB Output is correct
7 Correct 761 ms 61452 KB Output is correct
8 Correct 499 ms 61124 KB Output is correct
9 Correct 508 ms 67276 KB Output is correct
10 Correct 608 ms 62612 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 16340 KB Output is correct
2 Correct 866 ms 25480 KB Output is correct
3 Correct 2616 ms 25456 KB Output is correct
4 Correct 454 ms 25608 KB Output is correct
5 Correct 783 ms 25980 KB Output is correct
6 Correct 797 ms 25588 KB Output is correct
7 Correct 2601 ms 25716 KB Output is correct
8 Correct 418 ms 25476 KB Output is correct
9 Correct 809 ms 25964 KB Output is correct
10 Correct 832 ms 25644 KB Output is correct
11 Correct 2573 ms 25708 KB Output is correct
12 Correct 10 ms 16212 KB Output is correct
13 Correct 843 ms 214688 KB Output is correct
14 Correct 902 ms 220400 KB Output is correct
15 Correct 653 ms 212552 KB Output is correct
16 Correct 871 ms 262468 KB Output is correct
17 Correct 867 ms 221420 KB Output is correct
18 Correct 761 ms 61452 KB Output is correct
19 Correct 499 ms 61124 KB Output is correct
20 Correct 508 ms 67276 KB Output is correct
21 Correct 608 ms 62612 KB Output is correct
22 Execution timed out 8034 ms 224288 KB Time limit exceeded
23 Halted 0 ms 0 KB -