Submission #869450

#	Time	Username	Problem	Language	Result	Execution time	Memory
869450		AndreiBOTO	Toll (BOI17_toll)	C++14	100 / 100	126 ms	19828 KiB

toll

#include <bits/stdc++.h>

#pragma optimize GCC ("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

///#include <tryhardmode>
///#include <GODMODE::ON>

using namespace std;

const int NMAX=5e4+5;
const int INF=1e9;
const int KMAX=6;

vector<pair<int,int>>v[NMAX];

int dpst[NMAX][KMAX][KMAX];
int dpdr[NMAX][KMAX][KMAX];
int rez[NMAX];

int n,k;

struct elem{
    int st;
    int dr;
    int ind;
};
vector<elem>query[NMAX];

void divide(int st,int dr)
{
    int i,j;
    if(st==dr)
    {
        for(auto i:query[st])
            if(i.dr/k==st && i.st==i.dr)
                rez[i.ind]=0;
        return ;
    }
    else
    {
        int mij=st+dr;
        mij/=2;
        divide(st,mij);
        divide(mij+1,dr);
        for(int bucket=st;bucket<=mij;bucket++)
            for(i=0;i<k;i++)
                for(j=0;j<k;j++)
                    dpst[bucket][i][j]=INF;
        for(int bucket=dr;bucket>=mij;bucket--)
            for(i=0;i<k;i++)
                for(j=0;j<k;j++)
                    dpdr[bucket][i][j]=INF;
        for(i=0;i<k;i++)
            dpst[mij][i][i]=dpdr[mij][i][i]=0;
        ///dpst-> mij....st
        ///dpdr-> mij....dr
        for(int bucket=mij;bucket<dr;bucket++)
        {
            for(i=0;i<k;i++)
                for(j=0;j<k;j++)
                    for(auto edge:v[bucket*k+j])
                    {
                        dpdr[bucket+1][i][edge.first%k]=min(dpdr[bucket+1][i][edge.first%k],
                        dpdr[bucket][i][j]+edge.second);
                    }
        }
        for(int bucket=mij-1;bucket>=st;bucket--)
        {
            for(i=0;i<k;i++)
                for(j=0;j<k;j++)
                    for(auto edge:v[bucket*k+j])
                    {
                        dpst[bucket][i][j]=min(dpst[bucket][i][j],
                        dpst[bucket+1][i][edge.first%k]+edge.second);
                    }
        }
        for(i=st;i<=mij;i++)
            for(auto j:query[i])
                if(j.dr/k<=dr && j.dr/k>mij)
                    for(int lup=0;lup<k;lup++)
                        rez[j.ind]=min(rez[j.ind],dpst[i][lup][j.st%k]+dpdr[j.dr/k][lup][j.dr%k]);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int m,o,i,j;
    cin>>k>>n>>m>>o;
    for(i=1;i<=m;i++)
    {
        int x,y,c;
        cin>>x>>y>>c;
        v[x].push_back(make_pair(y,c));
    }
    for(i=1;i<=o;i++)
    {
        int x,y;
        cin>>x>>y;
        query[x/k].push_back({x,y,i});
        rez[i]=INF;
    }
    divide(0,n/k);
    for(i=1;i<=o;i++)
        if(rez[i]==INF)
            cout<<-1<<"\n";
        else
            cout<<rez[i]<<"\n";
    return 0;
}

Compilation message (stderr)

toll.cpp:3: warning: ignoring '#pragma optimize GCC' [-Wunknown-pragmas]
    3 | #pragma optimize GCC ("Ofast")
      | 
toll.cpp: In function 'int main()':
toll.cpp:93:15: warning: unused variable 'j' [-Wunused-variable]
   93 |     int m,o,i,j;
      |               ^

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