Submission #480925

#	Time	Username	Problem	Language	Result	Execution time	Memory
480925		DJeniUp	Toll (BOI17_toll)	C++17	25 / 100	3067 ms	10724 KiB

toll

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll>pairll;
typedef pair<ll,pairll>pairlll;
typedef pair<pairll,pairll>pairllll;
typedef long double ld;
typedef pair<ll,string>pairls;

#define INF 1000000000000007
#define MOD 1000000007
#define pb push_back
#define fr first
#define sc second
#define endl '\n'

ll k,n,m,o,res[10007],t[50007][7];

vector<pairll>v[50007];

struct D{
    ll l,r,q;
}d[10007];

bool mcp(D d1, D d2){
    return d1.l<d2.l;
}

int main() {
    
    cin>>k>>n>>m>>o;
    for(int i=1;i<=m;i++){
        ll l,r,c;
        cin>>l>>r>>c;
        v[r].pb({l,c});
    }
    for(int i=1;i<=o;i++){
        cin>>d[i].l>>d[i].r;
        d[i].q=i;
    }
    sort(d+1,d+1+o,mcp);
    ll x=0;
    for(int i=1;i<=o;i++){
        if(d[i].l/k!=d[i-1].l/k || i==1){
            x=d[i].l-d[i].l%k;
            for(int j=0;j<k;j++){
                t[x][j]=t[x+1][j]=t[x+2][j]=t[x+3][j]=t[x+4][j]=INF;
            }
            t[x][0]=t[x+1][1]=t[x+2][2]=t[x+3][3]=t[x+4][4]=0;
            for(int j=x+k;j<n;j++){
                for(int y=0;y<k;y++){
                    t[j][y]=INF;
                    for(auto it: v[j]){
                        t[j][y]=min(t[j][y],t[it.fr][y]+it.sc);
                    }
                }
            }
        }
        if(d[i].l>d[i].r || t[d[i].r][d[i].l%k]==INF)res[d[i].q]=-1;
        else res[d[i].q]=t[d[i].r][d[i].l%k];
    }
    for(int i=1;i<=o;i++){
        cout<<res[i]<<endl;
    }

}

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 0 / 31
• Subtask 5: 0 / 44