oj.uz

Submission #924499

# Submission time Handle Problem Language Result Execution time Memory
924499 2024-02-09T05:59:11 Z Faisal_Saqib Toll (BOI17_toll) C++17
0 / 100
 3000 ms 10072 KB 
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
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];
int 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: ";
            for(int& vertex:block[i/k])
            {
            	// cout<<vertex<<' ';
                Dist_this[index[vertex]][vertex]=0;
                for(auto& [adj,wei]:ma[vertex])
                {
                    Dist_this[index[vertex]][adj]=wei;
                    for(int to=max(block[adj/k].back(),i)+1;to<n;to++)
                    {
                        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]);
                    }
                }
            }
            // cout<<endl;
            for(int ind=0;ind<k;ind++)
            {
                for(int l=i+1;l<n;l++)
                {
                    Dist_next[ind][l]=Dist_this[ind][l];
                    // cout<<Dist_next[ind][l]<<' ';
                    Dist_this[ind][l]=1e9;
                }
                // cout<<endl;
            }
            // cout<<"change block\n";
        }
    }
    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 3091 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 3038 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 6492 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 2 ms 6488 KB Output is correct
4 Incorrect 2 ms 6492 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

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

Subtask #5
0 / 44.0

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