Submission #128728

#	Time	Username	Problem	Language	Result	Execution time	Memory
128728		SamAnd	Toll (BOI17_toll)	C++17	100 / 100	272 ms	22084 KiB

toll

#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
const int N = 50010, INF = 1000000009;

int k, n, m, q;
vector<pair<int, int> > a[N];

vector<vector<int> > b[N];

void make(vector<vector<int> >& vv)
{
    vector<int> v;
    for (int i = 0; i < k; ++i)
    {
        vv.push_back(v);
        for (int j = 0; j < k; ++j)
        {
            vv[i].push_back(INF);
        }
    }
}

vector<vector<int> > mer(const vector<vector<int> >& l, const vector<vector<int> >& r)
{
    vector<vector<int> > res;
    make(res);
    for (int x = 0; x < k; ++x)
    {
        for (int y = 0; y < k; ++y)
        {
            for (int z = 0; z < k; ++z)
            {
                res[x][y] = min(res[x][y], l[x][z] + r[z][y]);
            }
        }
    }
    return res;
}

vector<vector<int> > t[N * 4];
void bil(int tl, int tr, int pos)
{
    if (tr < tl)
        return;
    if (tl == tr)
    {
        t[pos] = b[tl];
        return;
    }
    int m = (tl + tr) / 2;
    bil(tl, m, pos * 2);
    bil(m + 1, tr, pos * 2 + 1);
    t[pos] = mer(t[pos * 2], t[pos * 2 + 1]);
}
vector<vector<int> > qry(int tl, int tr, int l, int r, int pos)
{
    if (tl == l && tr == r)
        return t[pos];
    int m = (tl + tr) / 2;
    if (r <= m)
        return qry(tl, m, l, r, pos * 2);
    if (l > m)
        return qry(m + 1, tr, l, r, pos * 2 + 1);
    return mer(qry(tl, m, l, m, pos * 2), qry(m + 1, tr, m + 1, r, pos * 2 + 1));
}

int main()
{
    scanf("%d%d%d%d", &k, &n, &m, &q);
    while (n % k != 0)
        ++n;
    for (int i = 0; i < m; ++i)
    {
        int x, y, d;
        scanf("%d%d%d", &x, &y, &d);
        a[x].push_back(m_p(y, d));
    }
    for (int i = 0; i < (n / k) - 1; ++i)
    {
        make(b[i]);
        for (int j = 0; j < k; ++j)
        {
            for (int jj = 0; jj < a[i * k + j].size(); ++jj)
            {
                pair<int, int> h = a[i * k + j][jj];
                b[i][j][h.first - (i + 1) * k] = min(b[i][j][h.first - (i + 1) * k], h.second);
            }
        }
    }
    bil(0, n / k - 2, 1);
    while (q--)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        int ll = l / k;
        int rr = r / k;
        if (ll >= rr)
        {
            printf("-1\n");
            continue;
        }
        vector<vector<int> > vv = qry(0, n / k - 2, ll, rr - 1, 1);
        if (vv[l % k][r % k] == INF)
            printf("-1\n");
        else
            printf("%d\n", vv[l % k][r % k]);
    }
    return 0;
}

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:84:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int jj = 0; jj < a[i * k + j].size(); ++jj)
                              ~~~^~~~~~~~~~~~~~~~~~~~~
toll.cpp:70:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%d", &k, &n, &m, &q);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &x, &y, &d);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
toll.cpp:95:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &l, &r);
         ~~~~~^~~~~~~~~~~~~~~~

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