oj.uz

답안 #979336

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
979336 2024-05-10T16:31:17 Z lftroq Toll (BOI17_toll) C++14
0 / 100
 54 ms 83680 KB 
/*

                                             :-=-
                                        :%@@@@@@@@@=
                                     .#@@@@@%@%@@@@@@=
                                    -@@@@@@@@@@@@@@@@@#
                                  .+@@@@@@@@@@@@@@@@@@@@.
                                  #@@@@@@@@@@@@@@@@@@@@@%
                                .*@@@@@@@@@@@@@@@@@@@@@@@=        ／￣￣￣￣￣￣￣￣￣＼
                                .@@@@@@@@@@@@@@@@@@@@@@@@#       |      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
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 54 ms 83680 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 40 ms 76376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 33116 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 33116 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 54 ms 83680 KB Output isn't correct
2 Halted 0 ms 0 KB -