Submission #979337

#	Time	Username	Problem	Language	Result	Execution time	Memory
979337		lftroq	Toll (BOI17_toll)	C++14	100 / 100	60 ms	83636 KiB

toll

/*

                                             :-=-
                                        :%@@@@@@@@@=
                                     .#@@@@@%@%@@@@@@=
                                    -@@@@@@@@@@@@@@@@@#
                                  .+@@@@@@@@@@@@@@@@@@@@.
                                  #@@@@@@@@@@@@@@@@@@@@@%
                                .*@@@@@@@@@@@@@@@@@@@@@@@=        ／￣￣￣￣￣￣￣￣￣＼
                                .@@@@@@@@@@@@@@@@@@@@@@@@#       |      lftroq ♥      |
                                +@@@@@@@@@@@%%@@@@@@@@@@@@-       ＼＿＿＿＿＿＿＿＿＿／
                               .%@@@@@@@@@@%##%@@@@@@@@@@@#        /／
                               -@@@@@@@@%%%%%%%%%@@@@@@@@@@:
                          -+-  =@@@@@%##%#%##**+#@@@@@@@@@@-
                          .+++.%@@@%##%%%%%%%#**+##%%@@@@@@+
                            +=*%@@@#*###%%#=--+=+*##%@@@@@@%.
                            :*+%@@*+**##*=======+***#@@@@@@@:
                             =+++**%@###*=++=-==++**#@@@@@@@:
                           .**===*%@@@##+=**#*==***@@@@@@@@@:
                          :+++=+*+%%@@%#==+*%#*+=++@@@@@@@@%
                          .**#*+*+**+%#+=---=***+==*@@@@@@@:
                          :**#*+=+**@%##*%#++++--=++#@@@@@@@+-::.
                         =%**###**#@@%*=*%%%%%*==++++%@@@@@@#=-----.
                      .%@@%***###@@@%*++%%%#*===+=++++%@@@@%*=-----=.
                      =**##+=+##@@@@=+%+=***#%@#+**++++%@@%+=-------=:
                    .++===++====@@@@+--==-=#%%%%+++*++++#%+=------==+=.
                   -++--=++-:::::=#@#----+--*%%*+**+++++++==-----===--+=
                   :*+=--++-::::::--=-----==-=%==+%%***++=---=---===-=++:
                    :*+--+=-::::::::---:----+=-=++##***===-::::-+----=*+:
                     .=--:::.:::-=-::---::--------++--=====-::::--:-==++
                     :=::::::--::::::--=+-:--++++==++--==:::-:::----==+=
                     *-:::::::.....:-++++++++++++++=+=---::::===-:------
                    :+:--:......:-+++++++++++++++++====---:--=-=----:-:=.
                    :==--:::.:=+++++++++++++++++++++-::===-:-===-----=--:
                    .+=--:::-:=+++++==++++++++++++++=--:.:-===+-------+=-.
                     .+==-----::-+++-:+++=====+++++++=--=======--:----==+=.
                     :+===-----------:-++====+++++++++=--==--+-:------==-::
                      +=====-::----+-::-+====+++++++++++=---==:-===:-==-==.
                      :+===========+-::::-----+++++++++++*=--======-=+=-=.
                       .=========++=-::::::----:::-++++++*+=+======+++==.
                          .=========-::::::-----:::=+++++**+=+**====-:.   .
                             *======-::::::::-:-----++++++++==++++++-
                             #======-:::::::::-------++++++++====+++=
                             =======-:::::::::----:::=+++++++=====+++
                             =====---:::::::::::------=++++++===+==++=
                             :===-:--:::::::::::-------+++++++===++=++
                             .===-:--:::::::::::::-----=+++++====++===.
                             .+=-::--::::::::::::-:-----++++++====++=+:
                             .=-:::--::::::::::::-------=+++++===-----+=
                             .=-:::--:::::::::::---------=++++==-----==+=.
                             .=-:::---:::::::::::---------+++===-----===++.
                             .=::::---:::::::-:-----------=++==-:-----===+-
                             .--:::---:::::::--------------=+=----==--===+-
                             .=::::---::::::::::-------===--==-------=--==:
                             .=--::--::::----:---:::::-:----:::-----======-
                             .=---:--:::---::::::--------------------==++++
*/
#include <bits/stdc++.h>
#define fastIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MOD 1000000007ll
#define MOD2 998244353ll
#define endl '\n'
#define PI acos(-1)
#define INFINITE 1000000000
#define INFINITE2 1000000000000000000ll
#define llll pair<ll,ll>
#define ldld pair<ld,ld>
#define fi first
#define se second
#define sqrt sqrtl
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

using namespace std;

int k,n,m,q;
int dp[17][50005][5][5],ans[5][5],temp[5][5];

void solve()
{
    cin >> k >> n >> m >> q;
    for(int i=0;i<17;i++) for(int j=0;j<=(n+k-1)/k;j++) for(int h=0;h<k;h++) for(int l=0;l<k;l++) dp[i][j][h][l]=INFINITE;
    while(m--)
    {
        int u,v,w;
        cin >> u >> v >> w;
        dp[0][u/k][u%k][v%k]=w;
    }
    for(int i=1;i<17;i++)
    {
        for(int j=0;j+(1<<i)+1<=(n+k-1)/k;j++)
        {
            for(int u=0;u<k;u++)
            {
                for(int v=0;v<k;v++)
                {
                    for(int t=0;t<k;t++) dp[i][j][u][v]=min(dp[i][j][u][v],dp[i-1][j][u][t]+dp[i-1][j+(1<<(i-1))][t][v]);
                }
            }
        }
    }
    while(q--)
    {
        int a,b;
        cin >> a >> b;
        for(int i=0;i<k;i++)
        {
            for(int j=0;j<k;j++) ans[i][j]=INFINITE;
            ans[i][i]=0;
        }
        int x=a/k,y=b/k;
        for(int i=16;i>=0;i--)
        {
            if(x+(1<<i)<=y)
            {
                for(int u=0;u<k;u++) for(int v=0;v<k;v++) temp[u][v]=INFINITE;
                for(int u=0;u<k;u++) for(int v=0;v<k;v++) for(int t=0;t<k;t++) temp[u][v]=min(temp[u][v],ans[u][t]+dp[i][x][t][v]);
                for(int u=0;u<k;u++) for(int v=0;v<k;v++) ans[u][v]=temp[u][v];
                x+=(1<<i);
            }
        }
        if(ans[a%k][b%k]==INFINITE) cout << -1 << endl; else cout << ans[a%k][b%k] << endl;
    }
}

int main()
{
    fastIO
    //freopen("hanhhhh.inp","r",stdin);
    //freopen("hanhhhh.out","w",stdout);
    int t=1;
    //cin >> t;
    while(t--)
    solve();
    return 0;
}

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