oj.uz

Submission #924528

# Submission time Handle Problem Language Result Execution time Memory
924528 2024-02-09T07:22:14 Z Faisal_Saqib Toll (BOI17_toll) C++17
7 / 100
 3000 ms 4140 KB 
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
// #define int long long
const int N=5e4+2;
vector<pair<int,int>> ma[N];//,query[N];
// vector<int> block[N];
// int index[N];
// bool vis[N];
// int ans[N];
int Dist[N][6][6];
int ans[6][6];
int ans_[6][6];
signed main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int k,n,m,q;
    cin>>k>>n>>m>>q;
    for(int j=0;j<m;j++)
    {
        int a,b,t;
        cin>>a>>b>>t;
        ma[a].push_back({b,t});
    }
    // for(int lp=0;lp<q;lp++)
    // {
    //     int x,y;
    //     cin>>x>>y;
    //     query[x].push_back({y,lp});
    // }
    // for(int i=0;i<n;i++)
    // {
    //     index[i]=block[i/k].size();
    //     block[(i/k)].push_back(i);
    // }
    // for(int l=0;l<n;l++)
    //     for(int ind=0;ind<k;ind++)
    //         for(int p=0;p<k;p++)
    //             Dist[l][ind][p]=1e9;
    // for(int i=0;i<n;i++)
    //     Dist[(i/k)][i%k][i%k]=we;
    for(int lp=0;lp<q;lp++)
    {
        int x,y;
        cin>>x>>y;
        int cur_block=x/k;
        int block_to=y/k;
        for(int i=0;i<k;i++)
            for(int j=0;j<k;j++)
                ans_[i][j]=1e9;
        for(int i=0;i<k;i++)
            for(int j=0;j<k;j++)
                ans[i][j]=((i==j)?0:1e9);
        while(cur_block<block_to)
        {
            for(int j=0;j<k;j++)
            {
                for(int i=0;i<k;i++)
                {
                    for(auto& [adj,we]:ma[(cur_block*k)+i])
                    {
                        ans_[i][adj%k]=min(ans_[i][adj%k],ans[j][i]+we);
                    }
                }
            }
            for(int j=0;j<k;j++)
            {
                for(int i=0;i<k;i++)
                {
                    ans[i][j]=ans_[i][j];
                    ans_[i][j]=1e9;
                    // cout<<ans[i][j]<<' ';
                }
                // cout<<endl;
            }
            // cout<<"Change\n";
            cur_block++;
        }
        int ansp=1e9;
        for(int i=0;i<k;i++)
        {
            ansp=min(ansp,ans[i][y%k]);
        }
        if(ansp==1e9)
        {
            cout<<-1<<endl;
        }
        else
        {
            cout<<ansp<<endl;
        }
    }
    return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1719 ms 3448 KB Output is correct
2 Correct 1 ms 1624 KB Output is correct
3 Correct 1 ms 1628 KB Output is correct
4 Correct 1 ms 1628 KB Output is correct
5 Correct 5 ms 1628 KB Output is correct
6 Correct 6 ms 1628 KB Output is correct
7 Correct 5 ms 1628 KB Output is correct
8 Correct 1704 ms 3964 KB Output is correct
9 Correct 1680 ms 4140 KB Output is correct
10 Correct 517 ms 1876 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3015 ms 3412 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

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

Subtask #4
0 / 31.0

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

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 1719 ms 3448 KB Output is correct
2 Correct 1 ms 1624 KB Output is correct
3 Correct 1 ms 1628 KB Output is correct
4 Correct 1 ms 1628 KB Output is correct
5 Correct 5 ms 1628 KB Output is correct
6 Correct 6 ms 1628 KB Output is correct
7 Correct 5 ms 1628 KB Output is correct
8 Correct 1704 ms 3964 KB Output is correct
9 Correct 1680 ms 4140 KB Output is correct
10 Correct 517 ms 1876 KB Output is correct
11 Execution timed out 3015 ms 3412 KB Time limit exceeded
12 Halted 0 ms 0 KB -