oj.uz

Submission #876224

# Submission time Handle Problem Language Result Execution time Memory
876224 2023-11-21T12:54:22 Z vjudge1 Treatment Project (JOI20_treatment) C++17
0 / 100
 700 ms 524288 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Runtime error 700 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12940 KB Output is correct
2 Correct 3 ms 12936 KB Output is correct
3 Correct 3 ms 12892 KB Output is correct
4 Incorrect 2 ms 12936 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12940 KB Output is correct
2 Correct 3 ms 12936 KB Output is correct
3 Correct 3 ms 12892 KB Output is correct
4 Incorrect 2 ms 12936 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Runtime error 700 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -