Submission #148108

#	Time	Username	Problem	Language	Result	Execution time	Memory
148108		WhipppedCream	Toll (BOI17_toll)	C++17	100 / 100	450 ms	19472 KiB

toll

#include <bits/stdc++.h>
#define ii pair<int, int>
#define X first
#define Y second
#define pb push_back
#define mp make_pair
#define vi vector<int>
#define vii vector< pair<int, int> >
typedef long long ll;
using namespace std;
int K;
vector< vector< vector<int> > >  mat;
vector< vector<int> > iden;
vii adj[50005];
struct node
{
    vector< vector<int> > dat;
    node *left, *right;
    node(){}
    node(vector< vector<int> > want, node *A, node *B)
    {
        dat.assign(K, vi(K, 0));
        dat = want;
        left = A, right = B;
    }
};
node* build(int L, int R)
{
    if(L == R) return new node(mat[L], NULL, NULL);
    node* res = new node(vector< vector<int> >(K, vi(K, 0)), NULL, NULL);
    res->left = build(L, (L+R)/2);
    res->right = build((L+R)/2+1, R);
    for(int i = 0; i< K; i++)
    {
        for(int j = 0; j< K; j++)
        {
            int best = 1e9;
            for(int k = 0; k< K; k++)
            {
                best = min(best, res->left->dat[i][k]+res->right->dat[k][j]);
            }
            res->dat[i][j] = best;
        }
    }
    return res;
}
node query(node* p, int L, int R, int i, int j)
{
    //printf("it's %d %d %d %d\n", L, R, i, j);
    if(i> R || j< L) return node(iden, NULL, NULL);
    if(i<= L && R<= j) return *p;
    node res(vector< vi >(K, vi(K, 0)), NULL, NULL);
    node x = query(p->left, L, (L+R)/2, i, j);
    node y = query(p->right, (L+R)/2+1, R, i, j);
    //printf("here for %d %d\n", L, R);
    for(int i = 0; i< K; i++)
    {
        for(int j = 0; j< K; j++)
        {
            int best = 1e9;
            for(int k = 0; k< K; k++)
            {
                best = min(best, x.dat[i][k]+y.dat[k][j]);
            }
            res.dat[i][j] = best;
        }
    }
    return res;
}
int main()
{
    int n, m, q;
    scanf("%d %d %d %d", &K, &n, &m, &q);
    mat.assign(n/K+1, vector< vector<int> >(K, vi(K, 1e9)));
    for(int i = 0; i< m; i++)
    {
        int a, b, w; scanf("%d %d %d", &a, &b, &w);
        adj[a].pb(ii(b, w));
        mat[a/K][a%K][b%K] = min(mat[a/K][a%K][b%K], w);
    }
    iden.assign(K, vi(K, 1e9));
    for(int i = 0; i< K; i++) iden[i][i] = 0;
    node *root = build(0, (n-1)/K-1);
    //printf("ok\n");
    while(q--)
    {
        int x, y; scanf("%d %d", &x, &y);
        //kprintf("hihi\n");
        if(x == y)
        {
            printf("0\n"); continue;
        }
        if(x> y) swap(x, y);
        int x1 = x/K, x2 = x%K;
        int y1 = y/K, y2 = y%K;
        if(x1 == y1)
        {
            printf("-1\n"); continue;
        }
        node tmp = query(root, 0, (n-1)/K-1, x1, y1-1);
        //printf("%d %d\n", x2, y2);
        int res = tmp.dat[x2][y2];
        if(res == 1e9) printf("-1\n");
        else printf("%d\n", res);
        /*
        vector< vector<int>
         > ans(K, vi(K, 0));
        for(int p = x1; p< y1; p++)
        {
            vector< vector<int> > rub(K, vi(K, 1e9));
            for(int i = 0; i< K; i++)
            {
                for(int j = 0; j< K; j++)
                {
                    for(int k = 0; k< K; k++)
                    {
                        rub[i][j] = min(rub[i][j], ans[i][k]+mat[p][k][j]);
                    }
                }
            }
            for(int i = 0; i< K; i++)
            {
                for(int j = 0; j< K; j++)
                {
                    printf("%d ", rub[i][j]);
                }
                printf("\n");
            }
            for(int i = 0; i< K; i++) for(int j = 0; j< K; j++) ans[i][j] = rub[i][j];
        }
        int res = ans[x2][y2];
        if(res == 1e9) printf("-1\n");
        else printf("%d\n", res);
        */
    }
    return 0;
}

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:73: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:77:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int a, b, w; scanf("%d %d %d", &a, &b, &w);
                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:87:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int x, y; scanf("%d %d", &x, &y);
                   ~~~~~^~~~~~~~~~~~~~~~~

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