oj.uz

답안 #924492

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
924492 2024-02-09T05:44:43 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=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;l<n;l++)
                {
                    if(ind<block[(i/k)].size() and block[(i/k)][ind]==l)
                        Dist_this[ind][l]=0;
                    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;
}

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:79:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |                     if(ind<block[(i/k)].size() and block[(i/k)][ind]==l)
      |                        ~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3090 ms 10072 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3003 ms 9044 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 2 ms 6492 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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 2 ms 6492 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

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3090 ms 10072 KB Time limit exceeded
2 Halted 0 ms 0 KB -