oj.uz

Submission #1093527

# Submission time Handle Problem Language Result Execution time Memory
1093527 2024-09-27T02:32:40 Z DucNguyen2007 Toll (BOI17_toll) C++14
7 / 100
 34 ms 10772 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
const int maxN=5e4+5,INF=1e9;
const ll inf=2e18;
int n,k,m,q,ans[maxN+1],d[maxN+1][7][2];
vector<pii> adj[maxN+1],adj_rv[maxN+1];
struct query
{
    int l,r,id;
};
vector<query> p;
struct duongdi
{
    int u,w;
    bool operator < (const duongdi &o)const
    {
        return w>o.w;
    }
};
priority_queue<duongdi> pq;
void clr(int l,int r,int id)
{
    for(int i=l;i<=r;i++)
    {
        d[i][id][0]=d[i][id][1]=INF;
    }
}
void dijkstra(int s,int t,int type,int l,int r,vector<pii> adj[])
{
    d[s][t][type]=0;
    pq.push({s,0});
    while(!pq.empty())
    {
        duongdi tmp=pq.top();
        int u=tmp.u,w=tmp.w;
        //cout<<u<<" "<<w<<'\n';
        pq.pop();
        if(d[u][t][type]<w)
        {
            continue;
        }
        for(auto [v,nw]:adj[u])
        {

            if(v/k>r||v/k<l)
            {
                continue;
            }
            //cout<<v<<" "<<nw<<" "<<d[v][t][type]<<'\n';
            if(d[v][t][type]>d[u][t][type]+nw)
            {
                d[v][t][type]=d[u][t][type]+nw;
                pq.push({v,d[v][t][type]});
            }
        }
    }
}
void Dnc(int l,int r,vector<query> v)
{
    if(v.empty())
    {
        return;
    }
    if(l==r)
    {
        for(auto j:v)
        {
            ans[j.id]=0;
        }
        return;
    }
    int mid=(l+r)/2;
    for(int i=mid*k;i<(mid+1)*k;i++)
    {
        clr(l*k,(r+1)*k-1,i%k);
        dijkstra(i,i%k,0,l,mid,adj_rv);
        dijkstra(i,i%k,1,mid+1,r,adj);
    }
    vector<query> vec[2];
    for(auto j:v)
    {
        if(j.l/k<=mid&&mid<j.r/k)
        {
            int tmp=INF;
            //cout<<l<<" "<<r<<" "<<j.l<<" "<<j.r<<'\n';
            for(int i=0;i<k;i++)
            {
                tmp=min(tmp,d[j.l][i][0]+d[j.r][i][1]);
                //cout<<d[j.l][i][0]<<" "<<d[j.r][i][1]<<'\n';
            }
            if(tmp==INF)
            {
                ans[j.id]=-1;
            }
            else ans[j.id]=tmp;
        }
        if(l<=j.l/k&&j.r/k<=mid)
        {
            vec[0].push_back(j);
        }
        if(mid<j.l/k&&j.r/k<=r)
        {
            vec[1].push_back(j);
        }
    }
    Dnc(l,mid,vec[0]);
    Dnc(mid+1,r,vec[1]);
}
int main()
{
    //freopen("","r",stdin);
    //freopen("","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>k>>n>>m>>q;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        adj[u].push_back({v,w});
        adj_rv[v].push_back({u,w});
    }
    for(int i=1;i<=q;i++)
    {
        int l,r;
        cin>>l>>r;
        p.push_back({l,r,i});
    }
    Dnc(0,n/k,p);
    for(int i=1;i<=q;i++)
    {
        cout<<ans[i]<<'\n';
    }
}

Compilation message

toll.cpp: In function 'void dijkstra(int, int, int, int, int, std::vector<std::pair<int, int> >*)':
toll.cpp:48:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   48 |         for(auto [v,nw]:adj[u])
      |                  ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 10016 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2908 KB Output is correct
5 Correct 2 ms 2908 KB Output is correct
6 Correct 2 ms 2908 KB Output is correct
7 Correct 2 ms 2908 KB Output is correct
8 Correct 22 ms 9844 KB Output is correct
9 Correct 20 ms 9928 KB Output is correct
10 Correct 5 ms 5916 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 8.0

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

Subtask #4
0 / 31.0

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

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 10016 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2908 KB Output is correct
5 Correct 2 ms 2908 KB Output is correct
6 Correct 2 ms 2908 KB Output is correct
7 Correct 2 ms 2908 KB Output is correct
8 Correct 22 ms 9844 KB Output is correct
9 Correct 20 ms 9928 KB Output is correct
10 Correct 5 ms 5916 KB Output is correct
11 Correct 34 ms 10772 KB Output is correct
12 Correct 1 ms 2648 KB Output is correct
13 Incorrect 1 ms 2648 KB Output isn't correct
14 Halted 0 ms 0 KB -