Submission #1066091

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066091		vjudge1	Factories (JOI14_factories)	C++17	15 / 100	8071 ms	368844 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;
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 <= 10 && T <= 10){
        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 (stderr)

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 / 15
• Subtask 2: 0 / 18
• Subtask 3: 0 / 67