oj.uz

Submission #295283

# Submission time Handle Problem Language Result Execution time Memory
295283 2020-09-09T15:00:09 Z 최은수(#5799) Treatment Project (JOI20_treatment) C++17
0 / 100
 3000 ms 5340 KB 
#include<iostream>
#include<vector>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18;
const int mx=100010;
struct query
{
    int t,l,r,c;
    bool operator<(const query&x)const
    {
        return t<x.t;
    }
};
vector<pi>adj[mx];
ll dis[mx];
bool chk[mx];
inline void dijk(int n,int s)
{
    fill(dis,dis+n,INF);
    dis[s]=0;
    for(int i=0;i<n;i++)
    {
        int c=-1;
        ll mn=INF+1;
        for(int j=0;j<n;j++)
            if(!chk[j]&&dis[j]<mn)
                mn=dis[j],c=j;
        if(c==-1)
            break;
        chk[c]=1;
        for(pi&t:adj[c])
            dis[t.fi]=min(dis[t.fi],mn+t.se);
    }
    return;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    vector<query>qv(m);
    for(auto&t:qv)
        cin>>t.t>>t.l>>t.r>>t.c;
    for(int i=0;i<m;i++)
    {
        if(qv[i].l==1)
            adj[m+1].eb(i,qv[i].c);
        if(qv[i].r==n)
            adj[i].eb(m,0);
    }
    for(int i=0;i<m;i++)
    {
        for(int j=i+1;j<m;j++)
        {
            if(qv[i].t>qv[j].t)
            {
                if(qv[j].l+qv[i].t-qv[j].t<=qv[j].r-qv[i].t+qv[j].t&&
                qv[i].r+1>=qv[j].l+qv[i].t-qv[j].t&&qv[j].r-qv[i].t+qv[j].t+1>=qv[i].l)
                    adj[i].eb(j,qv[j].c),adj[j].eb(i,qv[i].c);
            }
            else
            {
                if(qv[i].l+qv[j].t-qv[i].t<=qv[i].r-qv[j].t+qv[i].t&&
                qv[i].r-qv[j].t+qv[i].t+1>=qv[j].l&&qv[j].r+1>=qv[i].l+qv[j].t-qv[i].t)
                    adj[i].eb(j,qv[j].c),adj[j].eb(i,qv[i].c);
            }
        }
    }
    dijk(m+2,m+1);
    if(dis[m]==INF)
        dis[m]=-1;
    cout<<dis[m]<<endl;
    return 0;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3051 ms 5340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Incorrect 2 ms 2816 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Incorrect 2 ms 2816 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3051 ms 5340 KB Time limit exceeded
2 Halted 0 ms 0 KB -