oj.uz

Submission #1063402

# Submission time Handle Problem Language Result Execution time Memory
1063402 2024-08-17T18:01:49 Z vjudge1 Factories (JOI14_factories) C++17
0 / 100
 8000 ms 50924 KB 
#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 en = max(tintout[u].fi.se, tintout[v].fi.se);
    for(int i = tintout[u].fi.fi; i >= 0; --i){
        if(tintout[euler_list[i]].fi.se >= en){
            return tintout[euler_list[i]].se;
        }
    }
    return u;
}

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]);
            //cout << LCA << endl;
            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:67: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]
   67 |     for(ll i = 0; i < euler_list.size(); ++i){
      |                   ~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 6232 KB Output is correct
2 Execution timed out 8068 ms 23640 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6232 KB Output is correct
2 Runtime error 207 ms 50924 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 6232 KB Output is correct
2 Execution timed out 8068 ms 23640 KB Time limit exceeded
3 Halted 0 ms 0 KB -