oj.uz

답안 #656622

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
656622 2022-11-08T02:39:21 Z Hiennoob123 공장들 (JOI14_factories) C++14
33 / 100
 8000 ms 262448 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/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 , 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

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 16340 KB Output is correct
2 Correct 882 ms 25480 KB Output is correct
3 Correct 2550 ms 25476 KB Output is correct
4 Correct 915 ms 25608 KB Output is correct
5 Correct 803 ms 25956 KB Output is correct
6 Correct 816 ms 25640 KB Output is correct
7 Correct 2556 ms 25452 KB Output is correct
8 Correct 1032 ms 25568 KB Output is correct
9 Correct 793 ms 26052 KB Output is correct
10 Correct 815 ms 25588 KB Output is correct
11 Correct 2550 ms 25684 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 16212 KB Output is correct
2 Correct 856 ms 214776 KB Output is correct
3 Correct 916 ms 220384 KB Output is correct
4 Correct 659 ms 212644 KB Output is correct
5 Correct 864 ms 262448 KB Output is correct
6 Correct 856 ms 221392 KB Output is correct
7 Correct 775 ms 61372 KB Output is correct
8 Correct 493 ms 61152 KB Output is correct
9 Correct 517 ms 67264 KB Output is correct
10 Correct 568 ms 62568 KB Output is correct

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 16340 KB Output is correct
2 Correct 882 ms 25480 KB Output is correct
3 Correct 2550 ms 25476 KB Output is correct
4 Correct 915 ms 25608 KB Output is correct
5 Correct 803 ms 25956 KB Output is correct
6 Correct 816 ms 25640 KB Output is correct
7 Correct 2556 ms 25452 KB Output is correct
8 Correct 1032 ms 25568 KB Output is correct
9 Correct 793 ms 26052 KB Output is correct
10 Correct 815 ms 25588 KB Output is correct
11 Correct 2550 ms 25684 KB Output is correct
12 Correct 14 ms 16212 KB Output is correct
13 Correct 856 ms 214776 KB Output is correct
14 Correct 916 ms 220384 KB Output is correct
15 Correct 659 ms 212644 KB Output is correct
16 Correct 864 ms 262448 KB Output is correct
17 Correct 856 ms 221392 KB Output is correct
18 Correct 775 ms 61372 KB Output is correct
19 Correct 493 ms 61152 KB Output is correct
20 Correct 517 ms 67264 KB Output is correct
21 Correct 568 ms 62568 KB Output is correct
22 Execution timed out 8102 ms 224136 KB Time limit exceeded
23 Halted 0 ms 0 KB -