Submission #282343

#	Time	Username	Problem	Language	Result	Execution time	Memory
282343		MKopchev	Railway Trip (JOI17_railway_trip)	C++14	20 / 100	2078 ms	9716 KiB

railway_trip

#include<bits/stdc++.h>
using namespace std;

const int nmax=1e5+42;

int n,k,q,inp[nmax];

stack<int> active_l,active_r;

vector<int> adj[nmax];

void add_edge(int u,int v)
{
    adj[u].push_back(v);
    adj[v].push_back(u);

    //cout<<"edge "<<u<<" "<<v<<endl;
}

int dist[nmax];

priority_queue< pair<int/*dist*/,int/*node*/> > pq,idle;

int dij(int from,int to)
{
    memset(dist,-1,sizeof(dist));

    pq=idle;

    pq.push({0,from});

    while(dist[to]==-1)
    {
        pair<int/*dist*/,int/*node*/> tp=pq.top();
        pq.pop();

        if(dist[tp.second]!=-1)continue;

        tp.first=-tp.first;

        //cout<<tp.first<<" "<<tp.second<<endl;

        dist[tp.second]=tp.first;

        for(auto k:adj[tp.second])
            pq.push({-(dist[tp.second]+1),k});
    }
    return dist[to]-1;
}
int query()
{
    int u,v;
    scanf("%i%i",&u,&v);

    return dij(u,v);
}
int main()
{
    scanf("%i%i%i",&n,&k,&q);

    for(int i=1;i<=n;i++)scanf("%i",&inp[i]);

    active_l.push(1);

    for(int i=2;i<=n;i++)
    {
        while(inp[active_l.top()]<inp[i])active_l.pop();

        add_edge(active_l.top(),i);

        active_l.push(i);
    }

    active_r.push(n);

    for(int i=n-1;i>=1;i--)
    {
        while(inp[active_r.top()]<inp[i])active_r.pop();

        add_edge(active_r.top(),i);

        active_r.push(i);
    }

    for(int i=1;i<=q;i++)
    {
        printf("%i\n",query());
    }
    return 0;
}

Compilation message (stderr)

railway_trip.cpp: In function 'int query()':
railway_trip.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   53 |     scanf("%i%i",&u,&v);
      |     ~~~~~^~~~~~~~~~~~~~
railway_trip.cpp: In function 'int main()':
railway_trip.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   59 |     scanf("%i%i%i",&n,&k,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
railway_trip.cpp:61:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   61 |     for(int i=1;i<=n;i++)scanf("%i",&inp[i]);
      |                          ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 0 / 25
• Subtask 4: 0 / 55