제출 #656756

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
656756		Hiennoob123	공장들 (JOI14_factories)	C++14	0 / 100	32 ms	28116 KiB

factories

#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() ;
    return ans ;
}

컴파일 시 표준 에러 (stderr) 메시지

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++) Tc[Set[i].se].clear() ;
      |                     ~^~~~~~~~~~~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 18
• Subtask 3: 0 / 67