oj.uz

Submission #628701

# Submission time Handle Problem Language Result Execution time Memory
628701 2022-08-13T15:37:44 Z Iwanttobreakfree Toll (BOI17_toll) C++17
0 / 100
 93 ms 4484 KB 
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define int long long
const int INF=1e18;
void dijkstra(int a,vector<vector<pair<int,int>>>& g,vector<int>& dist){
    for(int i=0;i<dist.size();i++)dist[i]=INF;
    dist[a]=0;
    priority_queue<pair<int,int>> pq;
    pq.push({0,a});
    while(pq.size()){
        int u=pq.top().second,d=-pq.top().first;
        pq.pop();
        if(d>dist[u])continue;
        for(auto v:g[u]){
            if(dist[v.first]>dist[u]+v.second){
                dist[v.first]=dist[u]+v.second;
                pq.push({-dist[v.first],v.first});
            }
        }
    }
}
void build(int n,int l,int r,vector<int>& t,vector<int>& li){
    if(l==r)t[n]=li[l];
    else{
        int mid=(r+l)/2;
        build(n<<1,l,mid,t,li);
        build((n<<1)+1,mid+1,r,t,li);
        t[n]=min(INF,t[n<<1]+t[(n<<1)+1]);
    }
    //cout<<l<<' '<<r<<' '<<t[n]<<'\n';
}
int val(int n,int l,int r,vector<int>& t,int a,int b){
    if(a>b)return INF;
    if(l>b||r<a)return 0;
    if(l>=a&&r<=b)return t[n];
    int mid=(r+l)/2;
    int vall=val(n<<1,l,mid,t,a,b);
    int valr=val((n<<1)+1,mid+1,r,t,a,b);
    return max(INF,vall+valr);
}
signed main(){
    int n,m,o,k,x,y,w;
    cin>>k>>n>>m>>o;
    if(k==1){
        vector<long long> dist(n,INF),t(n*4);
        dist[n-1]=0;
        while(m--){
            cin>>x>>y>>w;
            dist[x]=min(dist[x],w);
        }
        build(1,0,n-1,t,dist);
        while(o--){
            cin>>x>>y;
            int ans=val(1,0,n-1,t,x,y);
            if(ans==1e18)cout<<-1<<'\n';
            else cout<<ans<<'\n';
        }
    }else{
        vector<vector<pair<int,int>>> g(n,vector<pair<int,int>>());
        vector<long long> dist(n,INF);
        while(m--){
            cin>>x>>y>>w;
            //x--;y--;
            g[x].push_back({y,w});
            //g[y].push_back({x,w});
        }
        dijkstra(0,g,dist);
        while(o--){
            cin>>x>>y;
            if(dist[y]==1e18)cout<<-1<<'\n';
            else cout<<dist[y]<<'\n';
        }
    }
}

Compilation message

toll.cpp: In function 'void dijkstra(long long int, std::vector<std::vector<std::pair<long long int, long long int> > >&, std::vector<long long int>&)':
toll.cpp:8:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 |     for(int i=0;i<dist.size();i++)dist[i]=INF;
      |                 ~^~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 72 ms 2332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 72 ms 2332 KB Output isn't correct
2 Halted 0 ms 0 KB -