Submission #585159

#	Time	Username	Problem	Language	Result	Execution time	Memory
585159		Huy	Toll (BOI17_toll)	C++17	100 / 100	373 ms	62136 KiB

toll

#include<bits/stdc++.h>
//#define int long long
#define pii pair<int,ll>
#define fi first
#define se second
/*#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")*/
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ldb = long double;
const ll N = (int)1e9 + 1;
const int maxN = (int)5e4 + 5;
const int mod = 1e9 + 7;
//const int mod = 998244353;
const int infty = 1e15 + 7;
const int base = (int)4e5;

void InputFile()
{
    //freopen("scrivener.inp","r",stdin);
    //freopen("scrivener.out","w",stdout);
    //freopen("test.out","r",stdin);
}

void FastInput()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
}

int k,n,m,o;
ll f[maxN][17][5];
ll jump[maxN][5];
int grp;
map<pii,int> edg;

void Read()
{
    cin >> k >> n >> m >> o;
    for(int i = 1;i <= m;i++)
    {
        int a,b,t;
        cin >> a >> b >> t;
        edg[{a,b}] = edg[{b,a}] = t;
    }
}

void Solve()
{
    for(int i = n - 1;i >= 0;i--)
    {
        /// j = 0;
        for(int d = 0;d < k;d++)
        {
            int nxt = (i / k + 1) * k + d;
            if(edg.find(make_pair(i,nxt)) == edg.end()) f[i][0][d] = infty;
            else f[i][0][d] = edg[{i,nxt}];
        }

        for(int j = 1;j <= (int)log2(n);j++)
        {
            for(int d = 0;d < k;d++)
            {
                f[i][j][d] = infty;
                for(int d1 = 0;d1 < k;d1++) /// pre d
                {
                    int nxt = (i / k + (1<<(j-1))) * k + d1;
                    if(nxt <= n) f[i][j][d] = min(f[i][j][d],f[nxt][j-1][d] + f[i][j-1][d1]);
                    else
                    {
                        f[i][j][d] = min(f[i][j][d],f[i][j-1][d1]);
                    }
                }
            }
        }
    }

    while(o--)
    {
        int x,y;
        cin >> x >> y;
        if(x > y) cout << -1 <<'\n';
        else if(x / k == y / k)
        {
            if(x == y) cout << 0 <<'\n';
            else cout << -1 <<'\n';
        }
        else
        {
            int dis = y / k - x / k;
            int pre = x / k;
            for(int i = (int)log2(n);i >= 0;i--)
            {
                if(dis & (1 << i))
                {
                    int nxt = pre + (1 << i);
                    if(pre == x/k)
                    {
                        for(int d = 0;d < k;d++)
                        {
                            jump[nxt][d] = f[x][i][d];
                        }
                    }
                    else
                    {
                        for(int d = 0;d < k;d++)
                        {
                            jump[nxt][d] = infty;
                            for(int d1 = 0;d1 < k;d1++)
                            {
                                jump[nxt][d] = min(jump[nxt][d],jump[pre][d1]+f[pre*k+d1][i][d]);
                            }
                        }
                    }
                    pre = nxt;
                }
            }
            int res = jump[y/k][y%k];
            if(res >= infty) res = -1;
            cout << res <<'\n';
        }
    }

    //cout <<"dcme"<<' '<< f[4][0][2] <<' '<<'\n';
}

void Debug()
{

}


int32_t main()
{
    FastInput();
    //InputFile();
    //int sub_type;
    //cin >> sub_type;
    //Sieve();
    //Prepare();
    int test;
    //cin >> test;
    test = 1;
    while(test--)
        //for(int prc = 1; prc <= test; prc++)
    {
        Read();
        Solve();
        //Debug();
    }
}

Compilation message (stderr)

toll.cpp:19:24: warning: overflow in conversion from 'double' to 'int' changes value from '1.000000000000007e+15' to '2147483647' [-Woverflow]
   19 | const int infty = 1e15 + 7;
      |                   ~~~~~^~~

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