oj.uz

Submission #736891

# Submission time Handle Problem Language Result Execution time Memory
736891 2023-05-06T10:16:56 Z Cookie Passport (JOI23_passport) C++14
48 / 100
 991 ms 394596 KB 
#include<bits/stdc++.h>
#include<fstream>
using namespace std;
ifstream fin("WINTER.inp");
ofstream fout("WINTER.out");
 
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const ld PI = 3.14159265359;
const int x[4] = {1, -1, 0, 0};
const int y[4] = {0, 0, 1, -1};
const ll mod = 1e9 + 7;
const int mxn = 2e5, mxm = 1e5, sq = 400;
const int base = (1 << 18);
const ll inf = 1e9;
const ld pre = 1e-6;
struct th{
    int u, v, w;
};
int n, q;
int l[mxn + 1], r[mxn + 1], d[2505][2505];
vt<th>adj[2505][2505];
void add_edge(int a, int b, int c, int d, int w){
    adj[c][d].pb({a, b, w});
}
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    forr(i, 1, n + 1){
        cin >> l[i] >> r[i];
        forr(j, i, n + 1){
            d[i][j] = 1e9;
        }
    }
    for(int i = 1; i <= n; i++){
        int mnl = 1e9, mxr = -1;
        for(int j = i; j <= n; j++){
            mnl = min(mnl, l[j]); mxr = max(mxr, r[j]);
            if(i == j){
                add_edge(i, j, l[i], r[i], 1);
            }if(i < j){
                add_edge(i, j, i + 1, j, 0); add_edge(i, j, i, j - 1, 0);
            }
            add_edge(i, j, mnl, j, 1); add_edge(i, j, i, mxr, 1);
        }
    }
    d[1][n] = 0;
    deque<pair<int, int>>dq; dq.pb({1, n});
    while(!dq.empty()){
        auto [i, j] = dq.front(); dq.pop_front();
        for(auto [x, y, w]: adj[i][j]){
            if(d[x][y] > d[i][j] + w){
                d[x][y] = d[i][j] + w;
                if(w){
                    dq.pb({x, y});
                }else{
                    dq.push_front({x, y});
                }
            }
        }
    }
    cin >> q;
    forr(i, 0, q){
        int x; cin >> x;
        if(d[x][x] == 1e9)cout << -1 << "\n";
        else cout << d[x][x] << "\n";
    }
    return(0);
}

Compilation message

passport.cpp: In function 'int main()':
passport.cpp:60:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   60 |         auto [i, j] = dq.front(); dq.pop_front();
      |              ^
passport.cpp:61:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   61 |         for(auto [x, y, w]: adj[i][j]){
      |                  ^

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 147584 KB Output is correct
2 Correct 67 ms 147572 KB Output is correct
3 Correct 67 ms 147692 KB Output is correct
4 Runtime error 375 ms 352188 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 147648 KB Output is correct
2 Correct 67 ms 147648 KB Output is correct
3 Correct 67 ms 147692 KB Output is correct
4 Correct 67 ms 147660 KB Output is correct
5 Correct 70 ms 147708 KB Output is correct
6 Correct 76 ms 147652 KB Output is correct
7 Correct 69 ms 147716 KB Output is correct
8 Correct 69 ms 147728 KB Output is correct
9 Correct 67 ms 147692 KB Output is correct
10 Correct 69 ms 147672 KB Output is correct
11 Correct 81 ms 152004 KB Output is correct
12 Correct 80 ms 152196 KB Output is correct
13 Correct 77 ms 152308 KB Output is correct
14 Correct 76 ms 152032 KB Output is correct
15 Correct 80 ms 152396 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 147648 KB Output is correct
2 Correct 67 ms 147648 KB Output is correct
3 Correct 67 ms 147692 KB Output is correct
4 Correct 67 ms 147660 KB Output is correct
5 Correct 70 ms 147708 KB Output is correct
6 Correct 76 ms 147652 KB Output is correct
7 Correct 69 ms 147716 KB Output is correct
8 Correct 69 ms 147728 KB Output is correct
9 Correct 67 ms 147692 KB Output is correct
10 Correct 69 ms 147672 KB Output is correct
11 Correct 81 ms 152004 KB Output is correct
12 Correct 80 ms 152196 KB Output is correct
13 Correct 77 ms 152308 KB Output is correct
14 Correct 76 ms 152032 KB Output is correct
15 Correct 80 ms 152396 KB Output is correct
16 Correct 644 ms 353724 KB Output is correct
17 Correct 991 ms 387080 KB Output is correct
18 Correct 845 ms 377144 KB Output is correct
19 Correct 753 ms 370988 KB Output is correct
20 Correct 934 ms 363744 KB Output is correct
21 Correct 791 ms 394364 KB Output is correct
22 Correct 750 ms 377612 KB Output is correct
23 Correct 752 ms 380980 KB Output is correct
24 Correct 674 ms 380524 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 147648 KB Output is correct
2 Correct 67 ms 147648 KB Output is correct
3 Correct 67 ms 147692 KB Output is correct
4 Correct 67 ms 147660 KB Output is correct
5 Correct 70 ms 147708 KB Output is correct
6 Correct 76 ms 147652 KB Output is correct
7 Correct 69 ms 147716 KB Output is correct
8 Correct 69 ms 147728 KB Output is correct
9 Correct 67 ms 147692 KB Output is correct
10 Correct 69 ms 147672 KB Output is correct
11 Correct 81 ms 152004 KB Output is correct
12 Correct 80 ms 152196 KB Output is correct
13 Correct 77 ms 152308 KB Output is correct
14 Correct 76 ms 152032 KB Output is correct
15 Correct 80 ms 152396 KB Output is correct
16 Correct 644 ms 353724 KB Output is correct
17 Correct 991 ms 387080 KB Output is correct
18 Correct 845 ms 377144 KB Output is correct
19 Correct 753 ms 370988 KB Output is correct
20 Correct 934 ms 363744 KB Output is correct
21 Correct 791 ms 394364 KB Output is correct
22 Correct 750 ms 377612 KB Output is correct
23 Correct 752 ms 380980 KB Output is correct
24 Correct 674 ms 380524 KB Output is correct
25 Correct 75 ms 147680 KB Output is correct
26 Correct 70 ms 147656 KB Output is correct
27 Correct 642 ms 369112 KB Output is correct
28 Correct 958 ms 390344 KB Output is correct
29 Correct 940 ms 363888 KB Output is correct
30 Correct 749 ms 394596 KB Output is correct
31 Correct 664 ms 370144 KB Output is correct

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 147584 KB Output is correct
2 Correct 67 ms 147572 KB Output is correct
3 Correct 67 ms 147692 KB Output is correct
4 Runtime error 375 ms 352188 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -