oj.uz

Submission #1086816

# Submission time Handle Problem Language Result Execution time Memory
1086816 2024-09-11T14:22:59 Z Thanhs Passport (JOI23_passport) C++14
6 / 100
 605 ms 132200 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
// #define double long double
 
#define endl '\n'
#define fastIO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define setmin(x, y) x = min((x), (y))
#define setmax(x, y) x = max((x), (y))
#define sqr(x) ((x) * (x))
#define fi first
#define se second
#define aint(x) x.begin(), x.end()
 
// mt19937 hdp(chrono::high_resolution_clock::now().time_since_epoch().count());
// int rand(int l, int r){return l + ((hdp() % (r - l + 1)) + r - l + 1) % (r - l + 1);}

const int NM = 2e5 + 5;
const int inf = 1e9;

int pos[NM], n, ans[NM];
vector<pair<int, int>> g[4 * NM];

void build(int x = 1, int l = 1, int r = n)
{
    if (l == r)
    {
        pos[l] = x;
        return;
    }
    int m = l + r >> 1;
    build(x << 1, l, m);
    build(x << 1 | 1, m + 1, r);
    g[x << 1].emplace_back(x, 0);
    g[x << 1 | 1].emplace_back(x, 0);
    // cout << (x << 1) << ' ' << x << ' ' << 0 << endl;
    // cout << (x << 1 | 1) << ' ' << x << ' ' << 0 << endl;
}

void upd(int t, int l, int r, int x = 1, int lx = 1, int rx = n)
{
    if (l > rx || lx > r)
        return;
    if (lx >= l && rx <= r)
    {
        g[x].emplace_back(t, 1);
        // cout << x << ' ' << t << ' ' << 1 << endl;
        return;
    }
    int m = lx + rx >> 1;
    upd(t, l, r, x << 1, lx, m);
    upd(t, l, r, x << 1 | 1, m + 1, rx);
}

pair<int, int> a[NM];

vector<int> bfs(int s)
{
    vector<int> dist(4 * n + 1, inf);
    deque<pair<int, int>> dq;
    for (int i = 1; i <= n; i++)
    {
        if (a[i].fi == 1 && a[i].se == n)
        {
            dist[pos[i]] = 1;
            dq.push_front({1, pos[i]});
        }
    }
    dist[s] = 0;
    dq.push_front({0, s});
    while (!dq.empty())
    {
        auto u = dq.front();
        dq.pop_front();
        if (u.fi != dist[u.se])
            continue;
        for (auto v : g[u.se])
            if (dist[v.fi] > u.fi + v.se)
            {
                dist[v.fi] = u.fi + v.se;
                if (v.se)
                    dq.push_back({dist[v.fi], v.fi});
                else
                    dq.push_front({dist[v.fi], v.fi});
            }
    }
    return dist;
}

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;

void solve()
{
    cin >> n;
    build();
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i].fi >> a[i].se;
        upd(pos[i], a[i].fi, a[i].se);
    }
    vector<int> dist1 = bfs(pos[1]), dist2 = bfs(pos[n]);
    vector<int> dist(4 * n + 1);
    for (int i = 1; i < dist.size(); i++)
    {
        dist[i] = dist1[i] + dist2[i];
        if (dist[i] < inf)
            pq.push({dist[i], i});
    }
    for (int i = 1; i <= n; i++)
        if (a[i].fi == 1 && a[i].se == n)
        {
            dist[pos[i]] = 1;
            pq.push({1, pos[i]});
        }
    while (!pq.empty())
    {
        auto u = pq.top();
        pq.pop();
        if (u.fi != dist[u.se])
            continue;
        for (auto v : g[u.se])
            if (dist[v.fi] > u.fi + v.se)
            {
                dist[v.fi] = u.fi + v.se;
                pq.push({dist[v.fi], v.fi});
            }
    }
    for (int i = 1; i <= n; i++)
        ans[i] = (dist[pos[i]] < inf ? dist[pos[i]] : -1);
    int q; cin >> q;
    while (q--)
    {
        int x;
        cin >> x;
        cout << ans[x] << endl;
    }
}

signed main()
{
    fastIO
    if (fopen("in.txt", "r")) 
    {
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    }
    int tc = 1; // cin >> tc;
    while (tc--)
        solve();

}

Compilation message

passport.cpp: In function 'void build(long long int, long long int, long long int)':
passport.cpp:31:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |     int m = l + r >> 1;
      |             ~~^~~
passport.cpp: In function 'void upd(long long int, long long int, long long int, long long int, long long int, long long int)':
passport.cpp:50:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |     int m = lx + rx >> 1;
      |             ~~~^~~~
passport.cpp: In function 'void solve()':
passport.cpp:103:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |     for (int i = 1; i < dist.size(); i++)
      |                     ~~^~~~~~~~~~~~~
passport.cpp: In function 'int main()':
passport.cpp:144:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  144 |         freopen("in.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
passport.cpp:145:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  145 |         freopen("out.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19036 KB Output is correct
2 Correct 9 ms 19036 KB Output is correct
3 Correct 8 ms 19072 KB Output is correct
4 Correct 605 ms 132200 KB Output is correct
5 Correct 287 ms 83652 KB Output is correct
6 Correct 192 ms 73516 KB Output is correct
7 Correct 162 ms 80720 KB Output is correct
8 Correct 116 ms 73700 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19032 KB Output is correct
2 Correct 9 ms 19268 KB Output is correct
3 Correct 9 ms 19036 KB Output is correct
4 Correct 8 ms 19032 KB Output is correct
5 Correct 8 ms 19264 KB Output is correct
6 Correct 9 ms 19036 KB Output is correct
7 Correct 8 ms 19036 KB Output is correct
8 Incorrect 8 ms 19036 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19032 KB Output is correct
2 Correct 9 ms 19268 KB Output is correct
3 Correct 9 ms 19036 KB Output is correct
4 Correct 8 ms 19032 KB Output is correct
5 Correct 8 ms 19264 KB Output is correct
6 Correct 9 ms 19036 KB Output is correct
7 Correct 8 ms 19036 KB Output is correct
8 Incorrect 8 ms 19036 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19032 KB Output is correct
2 Correct 9 ms 19268 KB Output is correct
3 Correct 9 ms 19036 KB Output is correct
4 Correct 8 ms 19032 KB Output is correct
5 Correct 8 ms 19264 KB Output is correct
6 Correct 9 ms 19036 KB Output is correct
7 Correct 8 ms 19036 KB Output is correct
8 Incorrect 8 ms 19036 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19036 KB Output is correct
2 Correct 9 ms 19036 KB Output is correct
3 Correct 8 ms 19072 KB Output is correct
4 Correct 605 ms 132200 KB Output is correct
5 Correct 287 ms 83652 KB Output is correct
6 Correct 192 ms 73516 KB Output is correct
7 Correct 162 ms 80720 KB Output is correct
8 Correct 116 ms 73700 KB Output is correct
9 Correct 8 ms 19032 KB Output is correct
10 Correct 9 ms 19268 KB Output is correct
11 Correct 9 ms 19036 KB Output is correct
12 Correct 8 ms 19032 KB Output is correct
13 Correct 8 ms 19264 KB Output is correct
14 Correct 9 ms 19036 KB Output is correct
15 Correct 8 ms 19036 KB Output is correct
16 Incorrect 8 ms 19036 KB Output isn't correct
17 Halted 0 ms 0 KB -