Submission #423010

#	Time	Username	Problem	Language	Result	Execution time	Memory
423010		blue	Toll (BOI17_toll)	C++17	100 / 100	390 ms	19256 KiB

toll

#include <iostream>
#include <vector>
using namespace std;

const int maxN = 50000;
const int maxK = 5;
const int INF = 1e9;
const int no_ranges_used = -1;

//mod, cities, edges, orders
int K, N, M, O;

vector<int> edge[maxN];
vector<int> wt[maxN];

int X[maxK];
int curr_r = no_ranges_used;
vector< vector<int> > sample_mindist;

struct segtree
{
    int l; //l and r are over [i/K]
    int r;

    vector< vector<int> > minDist = sample_mindist;

    segtree* left = NULL;
    segtree* right = NULL;

    segtree()
    {
        ;
    }

    segtree(int L, int R)
    {
        l = L;
        r = R;

        if(l == r)
        {
            for(int m = 0; m < K; m++)
                minDist[m][m] = 0;
        }
        else
        {
            int m = (l+r)/2;
            left = new segtree(l, m);
            right = new segtree(m+1, r);

            for(int a = K*m; a < K*(m+1); a++)
            {
                for(int i = 0; i < edge[a].size(); i++)
                {
                    int b = edge[a][i];
                    int t = wt[a][i];

                    for(int m1 = 0; m1 < K; m1++)
                    {
                        for(int m2 = 0; m2 < K; m2++)
                        {
                            minDist[m1][m2] = min(minDist[m1][m2], left->minDist[m1][a%K] + t + right->minDist[b%K][m2]);
                        }
                    }
                }
            }
        }
    }

    void query(int A, int B) //ans is in X[B % K]
    {
        if(l == 0/K && r == (N-1)/K)
        {
            curr_r = no_ranges_used;
        }

        if(B/K < l || r < A/K) return;
        else if(A/K <= l && r <= B/K)
        {
            if(curr_r == no_ranges_used)
            {
                for(int m = 0; m < K; m++)
                {
                    X[m] = minDist[A%K][m];
                }
            }
            else
            {
                vector<int> Y(K, INF);

                for(int a = K*(l-1); a < K*l; a++)
                {
                    for(int i = 0; i < edge[a].size(); i++)
                    {
                        int b = edge[a][i];
                        int t = wt[a][i];

                        for(int m2 = 0; m2 < K; m2++)
                        {
                            Y[m2] = min(Y[m2], X[a % K] + t + minDist[b % K][m2]);
                        }
                    }
                }

                for(int m = 0; m < K; m++)
                    X[m] = Y[m];

            }
            curr_r = B%K;
        }
        else
        {
            left->query(A, B);
            right->query(A, B);
        }
    }
};

int main()
{
    cin >> K >> N >> M >> O;

    sample_mindist = vector< vector<int> >(K, vector<int>(K, INF));

    for(int e = 1; e <= M; e++)
    {
        int a, b, t;
        cin >> a >> b >> t;

        edge[a].push_back(b);
        wt[a].push_back(t);
    }

    segtree S(0/K, (N-1)/K);

    for(int o = 1; o <= O; o++)
    {
        int a, b;
        cin >> a >> b;

        S.query(a, b);
        if(X[b % K] >= INF) cout << "-1\n";
        else cout << X[b % K] << '\n';
    }
}

Compilation message (stderr)

toll.cpp: In constructor 'segtree::segtree(int, int)':
toll.cpp:53:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |                 for(int i = 0; i < edge[a].size(); i++)
      |                                ~~^~~~~~~~~~~~~~~~
toll.cpp: In member function 'void segtree::query(int, int)':
toll.cpp:93:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |                     for(int i = 0; i < edge[a].size(); i++)
      |                                    ~~^~~~~~~~~~~~~~~~

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