제출 #1063380

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1063380		vjudge1	공장들 (JOI14_factories)	C++17	0 / 100	37 ms	6236 KiB

factories

#include "factories.h"

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ll> vll;
typedef pair<long long, long long> pll;
typedef pair<char, ll> ci;
typedef pair<string, ll> si;
typedef long double ld;
typedef vector<ll> vi;
typedef vector<string> vs;
#define pb push_back
#define fi first
#define se second
#define whole(v) v.begin(), v.end()
#define rwhole(v) v.rbegin(), v.rend()
const ll inf = 10000000000000000;
#define fro front

vi euler_list;
vector<pair<ii, ll>> tintout(100005, pair<ii, ll>(ii(-1, -1), 0));
vector<vector<ii>> x(100005);
ll vis[100005];
ll hi[100005];

void euler(ll no,ll h){
    if(vis[no] != -1){
        return;
    }
    vis[no] = 1;
    hi[no] = h;
    euler_list.pb(no);
    for(auto e:x[no]){
        euler(e.fi, h + e.se);
    }
    euler_list.pb(no);
    return ;
}

ll lca(ll u, ll v){
    if(tintout[u].fi.fi > tintout[v].fi.fi){
        swap(u, v);
    }
    ll lo = 0;
    ll hi = tintout[u].fi.fi + 1;
    ll en = max(tintout[u].fi.se, tintout[v].fi.se);
    while(hi - lo > 1){
        ll mid = lo + (hi - lo) / 2;
        if(tintout[euler_list[mid]].fi.se >= en){
            lo = mid;
        }else{
            hi = mid;
        }
    }
    return tintout[lo].se;
}

void Init(int N, int A[], int B[], int D[]) {
    for(ll i = 0; i < N; ++i){
        x[A[i]].pb(ii(B[i], D[i]));
        x[B[i]].pb(ii(A[i], D[i]));
    }
    for(ll i = 0; i < 100005; ++i){
        tintout[i].second = i;
    }
    memset(vis, -1, sizeof vis);
    euler(0, 0);
    for(ll i = 0; i < euler_list.size(); ++i){
        if(tintout[euler_list[i]].fi.fi == -1)
            tintout[euler_list[i]].fi.fi = i;
        else{
            tintout[euler_list[i]].fi.se = i;
        }
    }
}

long long Query(int S, int X[], int T, int Y[]) {
    ll ans = inf;
    for(ll i = 0; i < S; ++i){
        for(ll j = 0; j < T; ++j){
            ll LCA = lca(X[i], Y[j]);
            ans = min(ans, hi[X[i]] - hi[LCA] + hi[Y[j]] - hi[LCA]);
        }
    }
    return ans;
}

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

factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:72:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     for(ll i = 0; i < euler_list.size(); ++i){
      |                   ~~^~~~~~~~~~~~~~~~~~~

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