oj.uz

Submission #924471

# Submission time Handle Problem Language Result Execution time Memory
924471 2024-02-09T05:01:00 Z Muhammad_Aneeq Toll (BOI17_toll) C++17
18 / 100
 1877 ms 524288 KB 
/*
بسم الله الرحمن الرحيم
Author:
                          (:Muhammad Aneeq:)
*/

#include <iostream>
#include <vector>
#include <queue>
#include <map>
using namespace std;
map<pair<int,int>,int>d;
int const N=5e4+10;
vector<pair<int,int>>nei[N]={};
int dist[N]={};
bool vis[N]={};
void bfs(int n)
{
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
    pq.push({0,n});
    dist[n]=0;
    while (pq.size())
    {
        int z=pq.top().second;
        pq.pop();
        if (vis[z])
            continue;
        vis[z]=1;
        for (auto [j,w]:nei[z])
        {
            if (dist[j]>dist[z]+w)
            {
                dist[j]=dist[z]+w;
                pq.push({dist[j],j});
            }
        }
    }
}
inline void solve()
{
    int n,m,k,o;
    cin>>k>>n>>m>>o;
    while (m--)
    {
        int a,b,t;
        cin>>a>>b>>t;
        nei[a].push_back({b,t});
    }
    vector<pair<int,int>>ord;
    bool w=1;
    while (o--)
    {
        int x,y;
        cin>>x>>y;
        w=(w&&(x==0));
        ord.push_back({x,y});
    }
    if (w)
    {   
        for (int i=0;i<n;i++)
            dist[i]=1e9+10,vis[i]=0;
        bfs(0);
        for (auto i:ord)
            cout<<(dist[i.second]==1e9+10?-1:dist[i.second])<<'\n';
    }
    else
    {
        for (auto i:ord)
        {
            if (d.find(i)!=d.end())
            {
                cout<<(d[i]==1e9+10?-1:d[i])<<'\n';
                continue;
            }
            for (int j=0;j<n;j++)
                dist[j]=1e9+10,vis[j]=0;
            bfs(i.first);
            for (int j=0;j<n;j++)
                d[{i.first,j}]=dist[j];
            cout<<(dist[i.second]==1e9+10?-1:dist[i.second])<<'\n';
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
        solve();
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 1739 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3676 KB Output is correct
2 Correct 1 ms 1628 KB Output is correct
3 Correct 1 ms 1628 KB Output is correct
4 Correct 1 ms 1628 KB Output is correct
5 Correct 1 ms 1628 KB Output is correct
6 Correct 1 ms 1628 KB Output is correct
7 Correct 3 ms 1884 KB Output is correct
8 Correct 3 ms 1884 KB Output is correct
9 Correct 13 ms 3596 KB Output is correct
10 Correct 45 ms 4604 KB Output is correct
11 Correct 26 ms 3676 KB Output is correct
12 Correct 18 ms 3416 KB Output is correct
13 Correct 37 ms 4388 KB Output is correct
14 Correct 23 ms 3408 KB Output is correct
15 Correct 20 ms 3164 KB Output is correct
16 Correct 19 ms 3160 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1624 KB Output is correct
2 Correct 1 ms 1628 KB Output is correct
3 Correct 1 ms 1624 KB Output is correct
4 Correct 1 ms 1628 KB Output is correct
5 Correct 1 ms 1628 KB Output is correct
6 Correct 14 ms 7592 KB Output is correct
7 Correct 16 ms 7368 KB Output is correct
8 Correct 21 ms 7256 KB Output is correct
9 Correct 21 ms 7512 KB Output is correct
10 Correct 1030 ms 316644 KB Output is correct
11 Correct 1291 ms 313740 KB Output is correct
12 Correct 1418 ms 317316 KB Output is correct
13 Correct 1352 ms 317796 KB Output is correct
14 Correct 1283 ms 316844 KB Output is correct
15 Correct 802 ms 189000 KB Output is correct
16 Correct 723 ms 190748 KB Output is correct

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1624 KB Output is correct
2 Correct 1 ms 1628 KB Output is correct
3 Correct 1 ms 1624 KB Output is correct
4 Correct 1 ms 1628 KB Output is correct
5 Correct 1 ms 1628 KB Output is correct
6 Correct 14 ms 7592 KB Output is correct
7 Correct 16 ms 7368 KB Output is correct
8 Correct 21 ms 7256 KB Output is correct
9 Correct 21 ms 7512 KB Output is correct
10 Correct 1030 ms 316644 KB Output is correct
11 Correct 1291 ms 313740 KB Output is correct
12 Correct 1418 ms 317316 KB Output is correct
13 Correct 1352 ms 317796 KB Output is correct
14 Correct 1283 ms 316844 KB Output is correct
15 Correct 802 ms 189000 KB Output is correct
16 Correct 723 ms 190748 KB Output is correct
17 Runtime error 1877 ms 524288 KB Execution killed with signal 9
18 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Runtime error 1739 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -