oj.uz

Submission #768700

# Submission time Handle Problem Language Result Execution time Memory
768700 2023-06-28T12:35:29 Z danikoynov Passport (JOI23_passport) C++14
48 / 100
 2000 ms 667572 KB 
#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 3e5 + 10;

struct graph
{
    vector < vector < pair < int, int > > > adj;
    int dist[maxn], n;

    graph() {};

    graph(int _n)
    {
        n = _n;
        adj.resize(n + 1);
    }

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

    void bfs(int st)
    {
        for (int i = 1; i <= n; i ++)
        {
            dist[i] = 1e9;
        }

        deque < int > q;
        dist[st] = 0;
        q.push_back(st);
        while(!q.empty())
        {
            int v = q.front();
            q.pop_front();
            ///cout << "here " << v << " " << dist[v] << endl;
            for (pair < int, int > nb : adj[v])
            {
                if (dist[nb.first] > dist[v] + nb.second)
                {
                    dist[nb.first] = dist[v] + nb.second;
                    if (nb.second == 0)
                        q.push_front(nb.first);
                    else
                        q.push_back(nb.first);
                }
            }
        }
    }
};

int n, q, l[maxn], r[maxn];
int a[maxn], b[maxn];
void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i ++)
    {
        cin >> l[i] >> r[i];
    }

    graph st(n + 1);
    for (int i = 1; i <= n; i ++)
    {
        for (int j = l[i]; j <= r[i]; j ++)
            st.add_edge(j, i, 1);
            ///cout << j << " " << i << " " << 1 << endl;
    }

    st.bfs(1);
    for (int i = 1; i <= n; i ++)
        a[i] = st.dist[i];
    st.bfs(n);
    for (int i = 1; i <= n; i ++)
        b[i] = st.dist[i];

        /**for (int i = 1; i <= n; i ++)
            cout << a[i] << " ";
        cout << endl;*/
    for (int i = 1; i <= n; i ++)
    {
        int edge = a[i] + b[i];
        if (a[i] > 0 && b[i] > 0)
            edge --;
        st.add_edge(n + 1, i, edge);
        ///cout << n + 1 << " " << i << " " << a[i] + b[i] - 1 << endl;
    }

    st.bfs(n + 1);

    cin >> q;
    for (int i = 1; i <= q; i ++)
    {
        int x;
        cin >> x;
        int ans = st.dist[x];
        if (ans > n)
            cout << -1 << endl;
        else
        cout << ans << endl;
    }



}

int main()
{
    speed();
    solve();
    return 0;
}
/**
9
1 1
2 2
3 3
1 4
2 8
5 7
4 9
8 8
9 9
1
6

*/

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 1 ms 1496 KB Output is correct
3 Correct 1 ms 1496 KB Output is correct
4 Execution timed out 2088 ms 667572 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1492 KB Output is correct
2 Correct 1 ms 1500 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 1 ms 1488 KB Output is correct
5 Correct 1 ms 1500 KB Output is correct
6 Correct 1 ms 1496 KB Output is correct
7 Correct 1 ms 1492 KB Output is correct
8 Correct 1 ms 1492 KB Output is correct
9 Correct 1 ms 1492 KB Output is correct
10 Correct 1 ms 1492 KB Output is correct
11 Correct 1 ms 1748 KB Output is correct
12 Correct 1 ms 1492 KB Output is correct
13 Correct 3 ms 2008 KB Output is correct
14 Correct 2 ms 2004 KB Output is correct
15 Correct 1 ms 1492 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1492 KB Output is correct
2 Correct 1 ms 1500 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 1 ms 1488 KB Output is correct
5 Correct 1 ms 1500 KB Output is correct
6 Correct 1 ms 1496 KB Output is correct
7 Correct 1 ms 1492 KB Output is correct
8 Correct 1 ms 1492 KB Output is correct
9 Correct 1 ms 1492 KB Output is correct
10 Correct 1 ms 1492 KB Output is correct
11 Correct 1 ms 1748 KB Output is correct
12 Correct 1 ms 1492 KB Output is correct
13 Correct 3 ms 2008 KB Output is correct
14 Correct 2 ms 2004 KB Output is correct
15 Correct 1 ms 1492 KB Output is correct
16 Correct 33 ms 17912 KB Output is correct
17 Correct 2 ms 2004 KB Output is correct
18 Correct 105 ms 34144 KB Output is correct
19 Correct 80 ms 32616 KB Output is correct
20 Correct 2 ms 1764 KB Output is correct
21 Correct 196 ms 6400 KB Output is correct
22 Correct 58 ms 38968 KB Output is correct
23 Correct 48 ms 28268 KB Output is correct
24 Correct 53 ms 29492 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1492 KB Output is correct
2 Correct 1 ms 1500 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 1 ms 1488 KB Output is correct
5 Correct 1 ms 1500 KB Output is correct
6 Correct 1 ms 1496 KB Output is correct
7 Correct 1 ms 1492 KB Output is correct
8 Correct 1 ms 1492 KB Output is correct
9 Correct 1 ms 1492 KB Output is correct
10 Correct 1 ms 1492 KB Output is correct
11 Correct 1 ms 1748 KB Output is correct
12 Correct 1 ms 1492 KB Output is correct
13 Correct 3 ms 2008 KB Output is correct
14 Correct 2 ms 2004 KB Output is correct
15 Correct 1 ms 1492 KB Output is correct
16 Correct 33 ms 17912 KB Output is correct
17 Correct 2 ms 2004 KB Output is correct
18 Correct 105 ms 34144 KB Output is correct
19 Correct 80 ms 32616 KB Output is correct
20 Correct 2 ms 1764 KB Output is correct
21 Correct 196 ms 6400 KB Output is correct
22 Correct 58 ms 38968 KB Output is correct
23 Correct 48 ms 28268 KB Output is correct
24 Correct 53 ms 29492 KB Output is correct
25 Correct 1 ms 1492 KB Output is correct
26 Correct 1 ms 1488 KB Output is correct
27 Correct 30 ms 18988 KB Output is correct
28 Correct 3 ms 2020 KB Output is correct
29 Correct 2 ms 1748 KB Output is correct
30 Correct 168 ms 6100 KB Output is correct
31 Correct 31 ms 21656 KB Output is correct

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 1 ms 1496 KB Output is correct
3 Correct 1 ms 1496 KB Output is correct
4 Execution timed out 2088 ms 667572 KB Time limit exceeded
5 Halted 0 ms 0 KB -