oj.uz

Submission #70066

# Submission time Handle Problem Language Result Execution time Memory
70066 2018-08-22T10:04:54 Z antimirage Arranging Tickets (JOI17_arranging_tickets) C++17
0 / 100
 5 ms 3448 KB 
#include <algorithm>
#include <iostream>
#include <assert.h>
#include <string.h>
#include <stdio.h>
#include <iomanip>
#include <utility>
#include <math.h>
#include <time.h>
#include <vector>
#include <set>
#include <map>
#include <queue>

#define fr first
#define sc second
#define mk make_pair
#define pb push_back
#define sz(s) (int)s.size()
#define all(s) s.begin(), s.end()

using namespace std;

const int N = 1e5 + 5;

int n, k, q, ar[N], u[N], a, b, used[N], v;

vector <int> g[N];

queue <int> qu;

main()
{
    cin >> n >> k >> q;

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

    for (int i = 1; i <= n; i++)
    {
        for (int j = i - 1; j >= 1; j--)
        {
            if (ar[j] >= ar[i])
            {
                g[i].pb(j);
                break;
            }
        }
        for (int j = i + 1; j <= n; j++)
        {
            if (ar[j] >= ar[i])
            {
                g[i].pb(j);
                break;
            }
        }
    }
    while (q--)
    {
        memset(u, -1, sizeof(u));
        memset(used, -1, sizeof(used));
        scanf("%d%d", &a, &b);

        v = a;

        qu.push(v);
        u[v] = 0;

        while (!qu.empty())
        {
            v = qu.front();
            qu.pop();
            for(auto to : g[v])
            {
                if ( u[to] == -1 )
                {
                    qu.push(to);
                    u[to] = u[v] + 1;
                }
            }
        }
        int ans = (u[b] == -1 ? 1e9 + 7 : u[b] - 1);

        v = b;

        qu.push(v);
        used[v] = 0;

        while (!qu.empty())
        {
            v = qu.front();
            qu.pop();
            for(auto to : g[v])
            {
                if ( used[to] == -1 )
                {
                    qu.push(to);
                    used[to] = used[v] + 1;
                }
            }
        }
        ans = (used[a] == -1 ? ans : used[a] - 1);

        for (int i = 1; i <= n; i++)
        {
            if (used[i] != -1 && u[i] != -1)
                ans = min(ans, used[i] + u[i] - 1);
        }
        printf("%d\n", ans);
    }
}

Compilation message

arranging_tickets.cpp: In function 'int main()':
arranging_tickets.cpp:37:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &ar[i]);
         ~~~~~^~~~~~~~~~~~~~
arranging_tickets.cpp:62:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 35.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 15.0

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