oj.uz

Submission #924503

# Submission time Handle Problem Language Result Execution time Memory
924503 2024-02-09T06:06:12 Z Faisal_Saqib Toll (BOI17_toll) C++17
0 / 100
 3000 ms 10072 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_next[6][N];
int Dist_this[6][N];
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 ind=0;ind<k;ind++)
        for(int l=0;l<n;l++)
            Dist_next[ind][l]=Dist_this[ind][l]=1e9;
    for(int i=n-1;i>=0;i--)
    {
        if(!vis[(i/k)])
        {
            vis[(i/k)]=1;
            // cout<<"Block: ";
            int st=block[i/k].back()+1;
            for(int& vertex:block[i/k])
            {
                // cout<<vertex<<' ';
                for(auto& [adj,wei]:ma[vertex]) // O(k)
                {
                    Dist_this[index[vertex]][adj]=wei;
                    for(int to=st;to<n;to++)
                    {
                        if(to>block[adj/k].back())
                            Dist_this[index[vertex]][to]=min(Dist_this[index[vertex]][to],Dist_next[index[adj]][to]+wei);
                    }
                }
                for(auto& [y,inp]:query[vertex])
                {
                    if(y==vertex)
                    {
                        ans[inp]=0;
                    }
                    else if(y<(i+1))
                    {
                        ans[inp]=-1;
                    }
                    else
                    {
                        ans[inp]=((Dist_this[index[vertex]][y]==1e9)?-1:Dist_this[index[vertex]][y]);
                    }
                }
            }
            for(int ind=0;ind<k;ind++)
            {
                for(int l=st;l<n;l++)
                {
                    Dist_next[ind][l]=Dist_this[ind][l];
                    Dist_this[ind][l]=1e9;
                }
            }
        }
    }
    for(int lp=0;lp<q;lp++)
        cout<<ans[lp]<<'\n';
    return 0;
}

Subtask #1
0 / 7.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 5 ms 6492 KB Output is correct
7 Correct 8 ms 6488 KB Output is correct
8 Correct 15 ms 6692 KB Output is correct
9 Correct 13 ms 6660 KB Output is correct
10 Execution timed out 3051 ms 9820 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 5 ms 6492 KB Output is correct
7 Correct 8 ms 6488 KB Output is correct
8 Correct 15 ms 6692 KB Output is correct
9 Correct 13 ms 6660 KB Output is correct
10 Execution timed out 3051 ms 9820 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

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