Submission #1086843

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086843		Thanhs	Passport (JOI23_passport)	C++14	100 / 100	622 ms	138548 KiB

passport

#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];
bool imp[4 * NM];

void build(int x = 1, int l = 1, int r = n)
{
    if (l == r)
    {
        imp[x] = (l != 1 && l != n);
        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;
    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] - imp[i];
        if (dist[i] < inf)
            pq.push({dist[i], 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++)
    {
        if (i == 1)
            ans[i] = (dist2[pos[1]] < inf ? dist2[pos[1]] : -1);
        else if (i == n)
            ans[i] = (dist1[pos[n]] < inf ? dist1[pos[n]] : -1);
        else
            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 (stderr)

passport.cpp: In function 'void build(long long int, long long int, long long int)':
passport.cpp:33:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |     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:52:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |     int m = lx + rx >> 1;
      |             ~~~^~~~
passport.cpp: In function 'void solve()':
passport.cpp:97: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]
   97 |     for (int i = 1; i < dist.size(); i++)
      |                     ~~^~~~~~~~~~~~~
passport.cpp: In function 'int main()':
passport.cpp:139:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  139 |         freopen("in.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
passport.cpp:140:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  140 |         freopen("out.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 8 / 8
• Subtask 5: 46 / 46