oj.uz

Submission #957636

# Submission time Handle Problem Language Result Execution time Memory
957636 2024-04-04T06:37:58 Z 12345678 Toll (BOI17_toll) C++17
7 / 100
 46 ms 31824 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=5e4+5, kx=16;

ll dp[nx][kx][5], sz, n, m, q, a, b, t;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>sz>>n>>m>>q;
    for (int i=0; i<nx; i++) for (int j=0; j<kx; j++) for (int k=0; k<sz; k++) dp[i][j][k]=1e18;
    for (int i=0; i<m; i++) cin>>a>>b>>t, dp[a][0][b%sz]=t;
    for (int i=1; i<kx; i++) for (int j=0; j<n; j++) for (int k=0; k<sz; k++) for (int l=0; l<sz; l++) dp[j][i][k]=min(dp[j][i][k], dp[j][i-1][l]+dp[min(l+((j/sz)+(1<<(i-1)))*sz, (ll)nx-1)][i-1][k]);
    //for (int i=0; i<n; i++) for (int j=0; j<3; j++) for (int k=0; k<sz; k++) cout<<i<<' '<<j<<' '<<k<<' '<<dp[i][j][k]<<'\n';
    while (q--)
    {
        cin>>a>>b;
        int c=a/sz, tg=b/sz;
        vector<pair<ll, ll>> v;
        v.push_back({0, a});
        if (c==t) 
        {
            cout<<-1<<'\n';
            continue;
        }
        for (int i=kx-1; i>=0; i--)
        {
            if (c+(1<<i)>tg) continue;
            if (v.empty())
            {
                cout<<-1<<'\n';
                break;
            }
            if (c+(1<<i)==tg)
            {
                ll res=1e18;
                for (auto x:v) res=min(res, x.first+dp[x.second][i][b%sz]);
                if (res==1e18) cout<<-1<<'\n';
                else cout<<res<<'\n';
                break;
            }
            vector<ll> tmp(sz, 1e18);
            for (int j=0; j<sz; j++) for (auto x:v) tmp[j]=min(tmp[j], x.first+dp[x.second][i][j]);
            v.clear();
            for (int j=0; j<sz; j++) if (tmp[j]!=1e18) v.push_back({tmp[j], (c+(1<<i))*sz+j});
            c+=(1<<i);
        }
    }
}

/*
5 14 5 0
0 5 9
5 12 10
0 7 7
7 12 8
4 7 10
0 12


*/

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 31824 KB Output is correct
2 Correct 5 ms 31576 KB Output is correct
3 Correct 5 ms 31580 KB Output is correct
4 Correct 5 ms 31580 KB Output is correct
5 Correct 6 ms 31580 KB Output is correct
6 Correct 6 ms 31580 KB Output is correct
7 Correct 7 ms 31580 KB Output is correct
8 Correct 31 ms 31748 KB Output is correct
9 Correct 34 ms 31760 KB Output is correct
10 Correct 20 ms 31616 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 31580 KB Output is correct
2 Correct 5 ms 31580 KB Output is correct
3 Incorrect 5 ms 31616 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 31580 KB Output is correct
2 Incorrect 5 ms 31580 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 31580 KB Output is correct
2 Incorrect 5 ms 31580 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 31824 KB Output is correct
2 Correct 5 ms 31576 KB Output is correct
3 Correct 5 ms 31580 KB Output is correct
4 Correct 5 ms 31580 KB Output is correct
5 Correct 6 ms 31580 KB Output is correct
6 Correct 6 ms 31580 KB Output is correct
7 Correct 7 ms 31580 KB Output is correct
8 Correct 31 ms 31748 KB Output is correct
9 Correct 34 ms 31760 KB Output is correct
10 Correct 20 ms 31616 KB Output is correct
11 Correct 46 ms 31580 KB Output is correct
12 Correct 5 ms 31580 KB Output is correct
13 Incorrect 5 ms 31616 KB Output isn't correct
14 Halted 0 ms 0 KB -