oj.uz

답안 #656602

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
656602 2022-11-08T02:18:48 Z Hiennoob123 공장들 (JOI14_factories) C++14
33 / 100
 8000 ms 409092 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<pll> T[500005]  ;
ll depth[500005] ;
ll dis[500005] ;
ll lg2[1000005] ;
ll Left[500005] ;
vector<ll> euler ;
vector<pll> 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) ;
    ll k = lg2[v-u+1] ;
    pll 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)
{
    ll 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 , 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<long long 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<long long 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<long long 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<long long 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<long long 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 20308 KB Output is correct
2 Correct 868 ms 30420 KB Output is correct
3 Correct 3033 ms 30596 KB Output is correct
4 Correct 452 ms 30600 KB Output is correct
5 Correct 777 ms 30976 KB Output is correct
6 Correct 787 ms 30624 KB Output is correct
7 Correct 2764 ms 30612 KB Output is correct
8 Correct 428 ms 30480 KB Output is correct
9 Correct 781 ms 30816 KB Output is correct
10 Correct 789 ms 30548 KB Output is correct
11 Correct 2761 ms 30612 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 20156 KB Output is correct
2 Correct 937 ms 374680 KB Output is correct
3 Correct 1029 ms 378584 KB Output is correct
4 Correct 740 ms 372412 KB Output is correct
5 Correct 975 ms 409092 KB Output is correct
6 Correct 975 ms 379976 KB Output is correct
7 Correct 915 ms 92780 KB Output is correct
8 Correct 641 ms 92436 KB Output is correct
9 Correct 635 ms 97312 KB Output is correct
10 Correct 691 ms 94004 KB Output is correct

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 20308 KB Output is correct
2 Correct 868 ms 30420 KB Output is correct
3 Correct 3033 ms 30596 KB Output is correct
4 Correct 452 ms 30600 KB Output is correct
5 Correct 777 ms 30976 KB Output is correct
6 Correct 787 ms 30624 KB Output is correct
7 Correct 2764 ms 30612 KB Output is correct
8 Correct 428 ms 30480 KB Output is correct
9 Correct 781 ms 30816 KB Output is correct
10 Correct 789 ms 30548 KB Output is correct
11 Correct 2761 ms 30612 KB Output is correct
12 Correct 11 ms 20156 KB Output is correct
13 Correct 937 ms 374680 KB Output is correct
14 Correct 1029 ms 378584 KB Output is correct
15 Correct 740 ms 372412 KB Output is correct
16 Correct 975 ms 409092 KB Output is correct
17 Correct 975 ms 379976 KB Output is correct
18 Correct 915 ms 92780 KB Output is correct
19 Correct 641 ms 92436 KB Output is correct
20 Correct 635 ms 97312 KB Output is correct
21 Correct 691 ms 94004 KB Output is correct
22 Execution timed out 8057 ms 384268 KB Time limit exceeded
23 Halted 0 ms 0 KB -