Submission #876224

#	Time	Username	Problem	Language	Result	Execution time	Memory
876224		vjudge1	Treatment Project (JOI20_treatment)	C++17	0 / 100	700 ms	524288 KiB

treatment

#include<bits/stdc++.h>
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxn=2e5;
const ll inf=1e18;
const ll mod=1e9+7;
ll n,m,t[maxn],l[maxn],r[maxn],c[maxn],d[maxn];
priority_queue<pli,vector<pli>,greater<pli>>pq;
vector<ll>g[maxn];
void solve()
{
    cin >> n >> m;
    for(int i=1;i<=m;i++)
    {
        cin >> t[i] >> l[i] >> r[i] >> c[i];
    }
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(i==j) continue;
            if(t[i]<=t[j])
            {
                if(l[j]<=r[i]-(t[j]-t[i])+1) g[i].pb(j);
            }
            else
            {
                if(r[i]>=l[j]+(t[i]-t[j])-1) g[i].pb(j);
            }
        }
    }
    for(int i=1;i<=m;i++)
    {
        d[i]=inf;
        if(l[i]==1)
        {
            d[i]=c[i];
            pq.push({d[i],i});
        }
    }
    while(!pq.empty())
    {
        ll u=pq.top().se;
        ll W=pq.top().fi;
        pq.pop();
        if(W>d[u]) continue;
        if(r[u]==n) {cout << W;return;}
        for(int v:g[u])
        {
            if(d[v]>d[u]+c[v])
            {
                d[v]=d[u]+c[v];
                pq.push({d[v],v});
            }
        }
    }
    cout << -1;
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

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