oj.uz

Submission #1066081

# Submission time Handle Problem Language Result Execution time Memory
1066081 2024-08-19T14:52:33 Z vjudge1 Factories (JOI14_factories) C++17
18 / 100
 8000 ms 383840 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;
vi euler_depth;
vector<pair<ii, ll>> tintout(500005, pair<ii, ll>(ii(-1, -1), 0));
vector<vector<ii>> x(500005);
ll vis[500005];
ll hi[500005];

struct segtree{
    ll dd, ht, mid;
    ll val;
    segtree *L, *R;
    segtree(ll l,ll r){
        dd = l, ht =r; mid = (dd+ht)/2;
        if(l == r){
            val = inf;
        }else{
            L = new segtree(dd, mid); R = new segtree(mid+1, ht);
            val = min(L -> val, R -> val);
        }
    }
    void update(ll pos, ll newval){
        if(dd == ht){
            val = newval;
        }else{
            if(pos <= mid){
                L -> update(pos, newval);
            }else{
                R -> update(pos, newval);
            }
            val = min(L -> val, R -> val);
        }
    }
    ll query(ll l, ll r){
        if(l == dd && r == ht) return val;
        if(r <= mid){
            return L -> query(l, r);
        }else if(l > mid){
            return R -> query(l, r);
        }
        return min(L -> query(l, mid), R -> query(mid+1, r));
    }
};
segtree tree(0, 2000005);

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


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 < 500005; ++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;
        tintout[euler_list[i]].fi.se = i;
        
    }
    for(int i = 0; i < euler_depth.size(); ++i){
        tree.update(i, euler_depth[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){
            int a = tintout[X[i]].fi.fi;
            int b = tintout[Y[j]].fi.fi;
            ll l = min(a, b);
            a = tintout[X[i]].fi.se;
            b = tintout[Y[j]].fi.se;
            ll r = max(a, b);
            ll LCA = tree.query(l, r);
            if(LCA == tintout[X[i]].fi.fi || LCA == tintout[Y[i]].fi.fi){
                ans = min(ans, abs(hi[X[i]]  - hi[Y[j]])) ;
            }
            ans = min(ans, hi[X[i]] - LCA + hi[Y[j]] - LCA);
        }
    }
    return ans;
}

Compilation message

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

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 279120 KB Output is correct
2 Execution timed out 8022 ms 287572 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 278864 KB Output is correct
2 Correct 2182 ms 362896 KB Output is correct
3 Correct 2689 ms 364740 KB Output is correct
4 Correct 2020 ms 373700 KB Output is correct
5 Correct 2257 ms 383840 KB Output is correct
6 Correct 2164 ms 366440 KB Output is correct
7 Correct 4944 ms 314972 KB Output is correct
8 Correct 2918 ms 314176 KB Output is correct
9 Correct 2964 ms 317312 KB Output is correct
10 Correct 3022 ms 315416 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 279120 KB Output is correct
2 Execution timed out 8022 ms 287572 KB Time limit exceeded
3 Halted 0 ms 0 KB -