oj.uz

Submission #282343

# Submission time Handle Problem Language Result Execution time Memory
282343 2020-08-24T10:24:39 Z MKopchev Railway Trip (JOI17_railway_trip) C++14
20 / 100
 2000 ms 9716 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3072 KB Output is correct
2 Correct 4 ms 3072 KB Output is correct
3 Correct 4 ms 3072 KB Output is correct
4 Correct 4 ms 3072 KB Output is correct
5 Correct 3 ms 3072 KB Output is correct
6 Correct 4 ms 3072 KB Output is correct
7 Correct 3 ms 3072 KB Output is correct
8 Correct 4 ms 3072 KB Output is correct
9 Correct 3 ms 3072 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 3200 KB Output is correct
2 Correct 739 ms 8184 KB Output is correct
3 Correct 746 ms 8084 KB Output is correct
4 Correct 870 ms 8124 KB Output is correct
5 Correct 922 ms 8056 KB Output is correct
6 Correct 1156 ms 8568 KB Output is correct
7 Correct 1266 ms 9460 KB Output is correct
8 Correct 376 ms 7256 KB Output is correct
9 Correct 514 ms 8696 KB Output is correct
10 Correct 467 ms 7928 KB Output is correct
11 Correct 712 ms 8312 KB Output is correct
12 Correct 729 ms 8460 KB Output is correct
13 Correct 759 ms 8440 KB Output is correct
14 Correct 746 ms 8384 KB Output is correct
15 Correct 725 ms 8444 KB Output is correct
16 Correct 712 ms 8340 KB Output is correct
17 Correct 1426 ms 9460 KB Output is correct
18 Correct 1168 ms 9460 KB Output is correct
19 Correct 1143 ms 8944 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2070 ms 8192 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2078 ms 9716 KB Time limit exceeded
2 Halted 0 ms 0 KB -