Submission #1020278

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020278		underwaterkillerwhale	Treatment Project (JOI20_treatment)	C++17	35 / 100	496 ms	524288 KiB

treatment

#include <bits/stdc++.h>
#define se              second
#define fs              first
#define mp              make_pair
#define pb              push_back
#define ll              long long
#define ii              pair<ll,ll>
#define ld              long double
#define SZ(v)           (int)v.size()
#define ALL(v)          v.begin(), v.end()
#define bit(msk, i)     ((msk >> i) & 1)
#define iter(id, v)     for(auto id : v)
#define rep(i,m,n)      for(int i=(m); i<=(n); i++)
#define reb(i,m,n)      for(int i=(m); i>=(n); i--)

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r)
{
    return uniform_int_distribution<ll> (l, r)(rd);
}

const int N  = 2e5 + 7;
const int Mod =1e9 + 7;
const int szBL = 916;
const ll INF = 1e18;
const int BASE = 137;


struct Data {
    ll T, L, R, C;
};

int n, m;
Data a[N];
vector<pair<ll,ll>> ke[N];
ll Dist[N];

void solution () {
    cin >> n >> m;
    rep (i, 1, m) {
        cin >> a[i].T >> a[i].L >> a[i].R >> a[i].C;
        --a[i].L;
    }
    rep (i, 1, m)
    rep (j, 1, m) {
        if (i == j) continue;
        if (a[i].T <= a[j].T) {
            if (a[i].R + a[i].T >= a[j].L + a[j].T) ke[i].push_back({j, a[j].C});
        }
        else {
            if (a[i].R - a[i].T >= a[j].L - a[j].T) ke[i].push_back({j, a[j].C});
        }
    }
    memset(Dist, 0x3f, sizeof Dist);
    priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> pq;
    rep (i, 1, m) {
        if (a[i].L == 0) {
            pq.push({a[i].C, i});
            Dist[i] = a[i].C;

        }
    }
    while (!pq.empty()) {
        int u = pq.top().se;
        if (a[u].R == n) {
            cout << Dist[u] <<"\n";
            return;
        }
        pq.pop();
        iter (&id, ke[u]) {
            ll v, w;
            tie (v, w) = id;
            if (Dist[v] > Dist[u] + w) {
                Dist[v] = Dist[u] + w;
                pq.push({Dist[v], v});
            }
        }
    }
    cout << -1 <<"\n";
}

#define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);
int main () {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
//    file ("c");
    int num_Test = 1;
//    cin >> num_Test;
    while (num_Test--)
        solution();
}
/*
1 2
*/

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