oj.uz

Submission #1063376

# Submission time Handle Problem Language Result Execution time Memory
1063376 2024-08-17T17:30:40 Z vjudge1 Factories (JOI14_factories) C++17
0 / 100
 40 ms 5208 KB 
#include "factories.h"

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ll> vll;
typedef pair<long long, long long> pll;
typedef pair<char, int> ci;
typedef pair<string, int> si;
typedef long double ld;
typedef vector<int> 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, int>> tintout(100005, pair<ii, int>(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;
}

Compilation message

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<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     for(ll i = 0; i < euler_list.size(); ++i){
      |                   ~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 5208 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4696 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 5208 KB Output isn't correct
2 Halted 0 ms 0 KB -