oj.uz

답안 #656609

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
656609 2022-11-08T02:25:29 Z Hiennoob123 공장들 (JOI14_factories) C++17
33 / 100
 8000 ms 262488 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*4)
    {
        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<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 26 ms 16488 KB Output is correct
2 Correct 858 ms 25580 KB Output is correct
3 Correct 2588 ms 25548 KB Output is correct
4 Correct 465 ms 25668 KB Output is correct
5 Correct 796 ms 26468 KB Output is correct
6 Correct 793 ms 26092 KB Output is correct
7 Correct 2563 ms 26140 KB Output is correct
8 Correct 419 ms 26060 KB Output is correct
9 Correct 782 ms 26452 KB Output is correct
10 Correct 802 ms 26208 KB Output is correct
11 Correct 2606 ms 25984 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 16212 KB Output is correct
2 Correct 861 ms 214652 KB Output is correct
3 Correct 925 ms 220612 KB Output is correct
4 Correct 657 ms 212604 KB Output is correct
5 Correct 886 ms 262488 KB Output is correct
6 Correct 867 ms 221532 KB Output is correct
7 Correct 757 ms 61416 KB Output is correct
8 Correct 508 ms 61100 KB Output is correct
9 Correct 538 ms 67472 KB Output is correct
10 Correct 602 ms 62652 KB Output is correct

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 16488 KB Output is correct
2 Correct 858 ms 25580 KB Output is correct
3 Correct 2588 ms 25548 KB Output is correct
4 Correct 465 ms 25668 KB Output is correct
5 Correct 796 ms 26468 KB Output is correct
6 Correct 793 ms 26092 KB Output is correct
7 Correct 2563 ms 26140 KB Output is correct
8 Correct 419 ms 26060 KB Output is correct
9 Correct 782 ms 26452 KB Output is correct
10 Correct 802 ms 26208 KB Output is correct
11 Correct 2606 ms 25984 KB Output is correct
12 Correct 10 ms 16212 KB Output is correct
13 Correct 861 ms 214652 KB Output is correct
14 Correct 925 ms 220612 KB Output is correct
15 Correct 657 ms 212604 KB Output is correct
16 Correct 886 ms 262488 KB Output is correct
17 Correct 867 ms 221532 KB Output is correct
18 Correct 757 ms 61416 KB Output is correct
19 Correct 508 ms 61100 KB Output is correct
20 Correct 538 ms 67472 KB Output is correct
21 Correct 602 ms 62652 KB Output is correct
22 Execution timed out 8057 ms 224516 KB Time limit exceeded
23 Halted 0 ms 0 KB -