Submission #991723

#	Time	Username	Problem	Language	Result	Execution time	Memory
991723		yusuf12360	Train (APIO24_train)	C++17	5 / 100	1095 ms	39504 KiB

train

#include "train.h"
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pii pair<int, int>
#define vi vector<int>
#define vvi vector<vi> 
#define pb push_back
#define fi first
#define se second
#define TII tuple<int, int, int>
#define ts to_string
#pragma gcc optimize("O3")
using namespace std;
const ll INF=1e18;
int MAX=0;

struct node{
    vi tr=vi(0);
    int l, r, mid;
    node *left=nullptr, *right=nullptr;

    node(int l=0, int r=0) : l(l), r(r), mid(l+r>>1) {}

    void extend() {
        if(l==r) return;
        if(!left) left=new node(l, mid);
        if(!right) right=new node(mid+1, r);
    }
    void update(int idx, int val) {
        tr.pb(val);
        if(l==r) return;
        extend();
        if(idx<=mid) left->update(idx, val);
        else right->update(idx, val);
    }
    void sortin() {
        sort(tr.begin(), tr.end());
        if(left) left->sortin();
        if(right) right->sortin();
    }
    int get(int ql, int qr, int lm) {
    	if(max(l, ql)>min(r, qr)) return 0;
    	if(ql<=l && r<=qr) return tr.end()-lower_bound(tr.begin(), tr.end(), lm);
    	int from_l=0, from_r=0;
    	if(left) from_l=left->get(ql, qr, lm);
    	if(right) from_r=right->get(ql, qr, lm);
    	return from_l+from_r;
    }
};

vector<vector<pair<int, ll>>> dist;

int this_is_not_map(int u, int ending) { // :(
    pair<int, ll> ser={ending, 0};
    auto it=lower_bound(dist[u].begin(), dist[u].end(), ser);
    assert(it->fi==ending);
    int ret=it-dist[u].begin();
    return ret;
}

ll solve(int n, int m, int w, 
    vi t, // biaya makanan per planet (n)
    vi x, vi y, // planet x ke y (m)
    vi a, vi b, // waktu berangkat dri a ke b (m)
    vi c, // biaya perkereta (m)
    vi l, vi r) // waktu makanan yang dibutuhkan (w)
{
	// compression
    set<int> s; s.insert(0);
    for(int p : a) s.insert(p);
    for(int p : b) s.insert(p);
    for(int p : l) s.insert(p);
    for(int p : r) s.insert(p);
    map<int, int> mp;
    
    for(int p : s) mp[p]=MAX++;

    for(int &p : a) p=mp[p];
    for(int &p : b) p=mp[p];
    for(int &p : l) p=mp[p];
    for(int &p : r) p=mp[p];

    node *root=new node(0, MAX);
    for(int i=0; i<w; i++) root->update(r[i], l[i]);
    root->sortin();
    vector<vector<tuple<int, int, int, ll>>> adj(n);

    dist.assign(n, vector<pair<int, ll>>(0));
    for(int i=0; i<m; i++) {
        dist[y[i]].pb({b[i], INF});
        adj[x[i]].pb(make_tuple(y[i], a[i], b[i], c[i]));
    }
    dist[0].pb({0, 0}); // ending time, minimum cost
    for(int i=0; i<n; i++) sort(dist[i].begin(), dist[i].end());

    priority_queue<tuple<ll, int, int>> pq; pq.push({0, 0, 0}); // dist, node, end
    while(!pq.empty()) {
        auto [cur, u, ending] = pq.top(); pq.pop();
        cur=-cur;
        if(dist[u][this_is_not_map(u, ending)].se!=cur) continue;

        // cout << u << ' ' << nop[ending] << " : " << cur << endl;

        for(auto p : adj[u]) {
            auto [v, st, en, rizz] = p;
            if(ending>st) continue;
            // cout << "EIFN" << endl;
            ll cost=rizz+1ll*t[u]*root->get(ending+1, st-1, ending+1);
            // cout << "EFINEI" << endl;

            int id=this_is_not_map(v, en);
            if(dist[v][id].se>cur+cost) {
                dist[v][id].se=cur+cost;
                pq.push(make_tuple(-dist[v][id].se, v, en));
            }
        }
    }
    ll ans=INF;
    for(auto p : dist[n-1]) ans=min(ans, p.se+1ll*t[n-1]*root->get(p.fi+1, MAX-1, p.fi+1));
    return ans==INF ? -1ll : ans;
}

Compilation message (stderr)

train.cpp:13: warning: ignoring '#pragma gcc optimize' [-Wunknown-pragmas]
   13 | #pragma gcc optimize("O3")
      | 
train.cpp: In constructor 'node::node(int, int)':
train.cpp:23:47: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 |     node(int l=0, int r=0) : l(l), r(r), mid(l+r>>1) {}
      |                                              ~^~

• Subtask 1: 5 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 30
• Subtask 4: 0 / 60