Submission #1277877

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277877		phuocrucpp	Passport (JOI23_passport)	C++20	48 / 100	1592 ms	834000 KiB

passport

/*ㅤ∧＿∧
　(　･∀･)
　(　つ┳⊃
ε (_)へ⌒ヽﾌ
 (　　(　･ω･)
 ◎―◎   ⊃  ⊃
BePhuongSuperSuwi
From TK4 - CHT
ㅤㅤ／ ⌒＼____
　 /・　　 ）　　\
　/ノへ ノ　　　 /|
ノ　　  ＼\ |/_/_/*/


#include<bits/stdc++.h>
#define task "main"
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
//#define int long long
#define pb push_back
#define fi first
#define se second
#define ii pair<int,int>
#define iii pair<int,ii>
#define iv pair<ii, ii>
#define base 341
#define MASK(i) (1ll << i)
#define oo 2e9
#define isOn(x,i) ((x) & MASK(i))
#define bitOn(x,i) ((x) | MASK(i))
#define bitOff(x,i) ((x) & ~MASK(i))
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define __lcm(a,b) (1ll * ((a) / __gcd((a), (b))) * (b))
using namespace std;
//using namespace __gnu_pbds;
const int maxn = 1e7 + 2;
int n, l[maxn], r[maxn], dist[maxn];
vector <ii> nen, g[maxn];

int idx(int i, int j) {
    return (i - 1) * n + j;
}

void bfs(int st) {
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            dist[idx(i, j)] = oo;
        }
    }

    deque <int> q;
    dist[st] = 0;
    q.push_back(st);
//    cout << st << endl;
    while(!q.empty()) {
        int z = q.front();
        q.pop_front();

        for (auto e : g[z]) {
            int x = e.fi, y = e.se;
            if (dist[x] > dist[z] + y) {
                dist[x] = dist[z] + y;
                if (y == 0) q.push_front(x);
                else q.push_back(x);
            }
        }
    }
}

main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    if(fopen(task".inp","r")) {
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> l[i] >> r[i];

    }

    for (int i = 1; i <= n; i++) {
        int minl = oo, maxl = -oo;
        for (int j = i; j <= n; j++) {
            minl = min(minl, l[j]);
            maxl = max(maxl, r[j]);
//            if (i == 2 && j == 3) {
//                cout << minl << " " << j << endl;
//                cout << i << " " << maxl << endl;
//            }
            g[idx(minl, j)].pb({idx(i, j), 1});
            g[idx(i, maxl)].pb({idx(i, j), 1});
            if (i + 1 <= j)
                g[idx(i + 1, j)].pb({idx(i, j), 0});
            if (j - 1 >= i)
                g[idx(i, j - 1)].pb({idx(i, j), 0});


            if (i == j) {
                g[idx(l[i], r[i])].pb({idx(i, j), 1});
            }
        }
    }


    bfs(idx(1, n));
    int t = 1; cin >>t;

    while(t--) {
        int st; cin >> st;
        if (dist[idx(st, st)] == oo) cout << "-1" << endl;
        else cout << dist[idx(st, st)] << endl;
    }


}

Compilation message (stderr)

passport.cpp:71:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   71 | main() {
      | ^~~~
passport.cpp: In function 'int main()':
passport.cpp:74:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
passport.cpp:75:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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