oj.uz

Submission #656758

# Submission time Handle Problem Language Result Execution time Memory
656758 2022-11-08T07:33:06 Z Hiennoob123 Factories (JOI14_factories) C++14
100 / 100
 2557 ms 299820 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]  ;
vector<ll> Tc[500005] ;
int depth[500005] ;
ll dis[500005] ;
int lg2[1000005] ;
int Left[500005] ;
bool check[500005] ;
ll sz[500005] ;
ll pa[500005] ;
ll type[500005] ;
vector<int> euler ;
vector<pair<int , int>> sparse[20] ;
pll val[500005] ;
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 ;
}
ll distance(ll u , ll v)
{
    int k = LCA(u , v) ;
    return dis[u]+dis[v]-2*dis[k] ;
}
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 ans = LLONG_MAX ;
void dfs_vir(ll v , ll par)
{
    //cout << v << " " << par << "\n" ;
    val[v] = {LLONG_MAX , LLONG_MAX} ;
    for(int i = 0; i< Tc[v].size() ; i++)
    {
        if(Tc[v][i]==par) continue ;
        dfs_vir(Tc[v][i] , v) ;
        val[v].fi = min(val[v].fi , val[Tc[v][i]].fi) ;
        val[v].se = min(val[v].se , val[Tc[v][i]].se) ;
    }
    if(type[v]==1) val[v].fi = min(val[v].fi , dis[v]) ;
    if(type[v]==2) val[v].se = min(val[v].se , dis[v]) ;
    if(val[v].fi!=LLONG_MAX&&val[v].se!=LLONG_MAX)
    {
        ans = min(ans , val[v].fi+val[v].se-2*dis[v]) ;
    }
}
ll Query(int N, int X[], int M, int Y[])
{
    vector<pll> S ;
    for(int i = 0 ; i< N ; i++)
    {
        S.push_back(mp(Left[X[i]] , X[i])) ;
        type[X[i]] = 1 ;
    }
    for(int i = 0 ; i< M ; i++)
    {
        S.push_back(mp(Left[Y[i]] , Y[i])) ;
        type[Y[i]] = 2 ;
    }
    sort(S.begin() , S.end()) ;
    vector<pll> Set ;
    for(int i = 1 ; i< S.size() ; i++)
    {
        ll k = LCA(S[i].se , S[i-1].se) ;
        Set.push_back(mp(Left[k] , k)) ;
    }
    for(int i = 0 ; i < S.size() ; i++)
    {
        Set.push_back(S[i]) ;
    }
    sort(Set.begin() , Set.end()) ;
    stack<ll> Stack ;
    Stack.push(Set[0].se) ;
    for(int i = 1 ; i< Set.size() ; i++)
    {
        if(Set[i].se==Set[i-1].se) continue ;
        while(!Stack.empty())
        {
            ll x = Stack.top() ;
            if(LCA(x , Set[i].se)==x)
            {
                Tc[x].push_back(Set[i].se) ;
                Tc[Set[i].se].push_back(x) ;
                break ;
            }
            else Stack.pop() ;
        }
        Stack.push(Set[i].se) ;
    }
    ans = LLONG_MAX ;
    dfs_vir(Set[0].se , -1) ;
    for(int i = 0 ; i< Set.size() ; i++)
    {
        Tc[Set[i].se].clear() ;
        type[Set[i].se] = 0 ;
    }
    return ans ;
}

Compilation message

factories.cpp: In function 'void build()':
factories.cpp:33:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         if((1<<i)>euler.size()) break ;
      |            ~~~~~~^~~~~~~~~~~~~
factories.cpp:37:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |             for(int j = 0 ; j< euler.size() ; j++)
      |                             ~^~~~~~~~~~~~~~
factories.cpp:45:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |             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:69: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]
   69 |     for(int i = 0 ; i< T[v].size() ; i++)
      |                     ~^~~~~~~~~~~~~
factories.cpp: In function 'void dfs_vir(long long int, long long int)':
factories.cpp:96:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |     for(int i = 0; i< Tc[v].size() ; i++)
      |                    ~^~~~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:125: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]
  125 |     for(int i = 1 ; i< S.size() ; i++)
      |                     ~^~~~~~~~~~
factories.cpp:130:23: 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]
  130 |     for(int i = 0 ; i < S.size() ; i++)
      |                     ~~^~~~~~~~~~
factories.cpp:137: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]
  137 |     for(int i = 1 ; i< Set.size() ; i++)
      |                     ~^~~~~~~~~~~~
factories.cpp:155: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]
  155 |     for(int i = 0 ; i< Set.size() ; i++)
      |                     ~^~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 28116 KB Output is correct
2 Correct 750 ms 42204 KB Output is correct
3 Correct 758 ms 38340 KB Output is correct
4 Correct 735 ms 38728 KB Output is correct
5 Correct 678 ms 38428 KB Output is correct
6 Correct 471 ms 37972 KB Output is correct
7 Correct 752 ms 38116 KB Output is correct
8 Correct 764 ms 38560 KB Output is correct
9 Correct 674 ms 38812 KB Output is correct
10 Correct 486 ms 38240 KB Output is correct
11 Correct 728 ms 38144 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 27988 KB Output is correct
2 Correct 1347 ms 252632 KB Output is correct
3 Correct 1693 ms 257492 KB Output is correct
4 Correct 1108 ms 250412 KB Output is correct
5 Correct 1285 ms 299244 KB Output is correct
6 Correct 1482 ms 258960 KB Output is correct
7 Correct 1182 ms 79980 KB Output is correct
8 Correct 871 ms 79308 KB Output is correct
9 Correct 875 ms 85672 KB Output is correct
10 Correct 1188 ms 81164 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 28116 KB Output is correct
2 Correct 750 ms 42204 KB Output is correct
3 Correct 758 ms 38340 KB Output is correct
4 Correct 735 ms 38728 KB Output is correct
5 Correct 678 ms 38428 KB Output is correct
6 Correct 471 ms 37972 KB Output is correct
7 Correct 752 ms 38116 KB Output is correct
8 Correct 764 ms 38560 KB Output is correct
9 Correct 674 ms 38812 KB Output is correct
10 Correct 486 ms 38240 KB Output is correct
11 Correct 728 ms 38144 KB Output is correct
12 Correct 17 ms 27988 KB Output is correct
13 Correct 1347 ms 252632 KB Output is correct
14 Correct 1693 ms 257492 KB Output is correct
15 Correct 1108 ms 250412 KB Output is correct
16 Correct 1285 ms 299244 KB Output is correct
17 Correct 1482 ms 258960 KB Output is correct
18 Correct 1182 ms 79980 KB Output is correct
19 Correct 871 ms 79308 KB Output is correct
20 Correct 875 ms 85672 KB Output is correct
21 Correct 1188 ms 81164 KB Output is correct
22 Correct 2299 ms 265360 KB Output is correct
23 Correct 2139 ms 261620 KB Output is correct
24 Correct 2557 ms 270476 KB Output is correct
25 Correct 2494 ms 271684 KB Output is correct
26 Correct 2319 ms 261160 KB Output is correct
27 Correct 2222 ms 299820 KB Output is correct
28 Correct 1552 ms 262488 KB Output is correct
29 Correct 2235 ms 260280 KB Output is correct
30 Correct 2243 ms 259040 KB Output is correct
31 Correct 2259 ms 260144 KB Output is correct
32 Correct 1167 ms 94432 KB Output is correct
33 Correct 824 ms 88884 KB Output is correct
34 Correct 1222 ms 79072 KB Output is correct
35 Correct 1202 ms 78764 KB Output is correct
36 Correct 1312 ms 79828 KB Output is correct
37 Correct 1310 ms 79672 KB Output is correct