oj.uz

Submission #1066099

# Submission time Handle Problem Language Result Execution time Memory
1066099 2024-08-19T15:03:08 Z vjudge1 Factories (JOI14_factories) C++17
33 / 100
 8000 ms 380024 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;
    if(S <= 20 && T <= 20){
        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);
            }
        }
    }else{
        priority_queue<ii, vector<ii>, greater<ii>> q;
        ll dist[500005];
        for(int i = 0; i < 500005; ++i){
            dist[i] = inf;
        }
        for(ll i = 0; i < S; ++i){
            q.push(ii(0, X[i]));
            dist[X[i]] = 0;
        }
        while(!q.empty()){
            ll price = q.top().fi;
            ll node = q.top().se;
            q.pop();
            if(price != dist[node]){
                continue;
            }
            for(auto e:x[node]){
                if(dist[e.fi] > dist[node] + e.se){
                    q.push(ii(price + e.se, e.fi));
                    dist[e.fi] = price + e.se;
                }
            }
        }
        for(int i = 0; i < T; ++i){
            ans = min(ans, dist[Y[i]]);
        }
    }
    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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 282708 KB Output is correct
2 Correct 1249 ms 300296 KB Output is correct
3 Correct 3385 ms 300368 KB Output is correct
4 Correct 2392 ms 300520 KB Output is correct
5 Correct 1159 ms 300372 KB Output is correct
6 Correct 1122 ms 300360 KB Output is correct
7 Correct 3367 ms 300368 KB Output is correct
8 Correct 2853 ms 300368 KB Output is correct
9 Correct 1204 ms 300608 KB Output is correct
10 Correct 1222 ms 300368 KB Output is correct
11 Correct 3415 ms 300368 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 282448 KB Output is correct
2 Correct 3485 ms 363104 KB Output is correct
3 Correct 3206 ms 361448 KB Output is correct
4 Correct 3344 ms 374056 KB Output is correct
5 Correct 3449 ms 380024 KB Output is correct
6 Correct 3401 ms 364288 KB Output is correct
7 Correct 5834 ms 314480 KB Output is correct
8 Correct 4911 ms 314760 KB Output is correct
9 Correct 4653 ms 315660 KB Output is correct
10 Correct 4625 ms 317236 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 282708 KB Output is correct
2 Correct 1249 ms 300296 KB Output is correct
3 Correct 3385 ms 300368 KB Output is correct
4 Correct 2392 ms 300520 KB Output is correct
5 Correct 1159 ms 300372 KB Output is correct
6 Correct 1122 ms 300360 KB Output is correct
7 Correct 3367 ms 300368 KB Output is correct
8 Correct 2853 ms 300368 KB Output is correct
9 Correct 1204 ms 300608 KB Output is correct
10 Correct 1222 ms 300368 KB Output is correct
11 Correct 3415 ms 300368 KB Output is correct
12 Correct 164 ms 282448 KB Output is correct
13 Correct 3485 ms 363104 KB Output is correct
14 Correct 3206 ms 361448 KB Output is correct
15 Correct 3344 ms 374056 KB Output is correct
16 Correct 3449 ms 380024 KB Output is correct
17 Correct 3401 ms 364288 KB Output is correct
18 Correct 5834 ms 314480 KB Output is correct
19 Correct 4911 ms 314760 KB Output is correct
20 Correct 4653 ms 315660 KB Output is correct
21 Correct 4625 ms 317236 KB Output is correct
22 Execution timed out 8084 ms 377448 KB Time limit exceeded
23 Halted 0 ms 0 KB -