oj.uz

Submission #736882

# Submission time Handle Problem Language Result Execution time Memory
736882 2023-05-06T10:08:25 Z Cookie Passport (JOI23_passport) C++14
16 / 100
 277 ms 226924 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[2005][2005];
vt<th>adj[2005][2005];
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:59:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   59 |         auto [i, j] = dq.front(); dq.pop_front();
      |              ^
passport.cpp:60:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   60 |         for(auto [x, y, w]: adj[i][j]){
      |                  ^

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 94792 KB Output is correct
2 Correct 45 ms 94732 KB Output is correct
3 Correct 43 ms 94732 KB Output is correct
4 Runtime error 277 ms 226924 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 47 ms 94668 KB Output is correct
2 Correct 45 ms 94704 KB Output is correct
3 Correct 54 ms 94616 KB Output is correct
4 Correct 44 ms 94664 KB Output is correct
5 Correct 46 ms 94680 KB Output is correct
6 Correct 44 ms 94640 KB Output is correct
7 Correct 44 ms 94752 KB Output is correct
8 Correct 44 ms 94700 KB Output is correct
9 Correct 43 ms 94768 KB Output is correct
10 Correct 51 ms 94668 KB Output is correct
11 Correct 61 ms 98992 KB Output is correct
12 Correct 55 ms 99232 KB Output is correct
13 Correct 52 ms 99288 KB Output is correct
14 Correct 50 ms 99020 KB Output is correct
15 Correct 53 ms 99484 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 94668 KB Output is correct
2 Correct 45 ms 94704 KB Output is correct
3 Correct 54 ms 94616 KB Output is correct
4 Correct 44 ms 94664 KB Output is correct
5 Correct 46 ms 94680 KB Output is correct
6 Correct 44 ms 94640 KB Output is correct
7 Correct 44 ms 94752 KB Output is correct
8 Correct 44 ms 94700 KB Output is correct
9 Correct 43 ms 94768 KB Output is correct
10 Correct 51 ms 94668 KB Output is correct
11 Correct 61 ms 98992 KB Output is correct
12 Correct 55 ms 99232 KB Output is correct
13 Correct 52 ms 99288 KB Output is correct
14 Correct 50 ms 99020 KB Output is correct
15 Correct 53 ms 99484 KB Output is correct
16 Runtime error 144 ms 224052 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 94668 KB Output is correct
2 Correct 45 ms 94704 KB Output is correct
3 Correct 54 ms 94616 KB Output is correct
4 Correct 44 ms 94664 KB Output is correct
5 Correct 46 ms 94680 KB Output is correct
6 Correct 44 ms 94640 KB Output is correct
7 Correct 44 ms 94752 KB Output is correct
8 Correct 44 ms 94700 KB Output is correct
9 Correct 43 ms 94768 KB Output is correct
10 Correct 51 ms 94668 KB Output is correct
11 Correct 61 ms 98992 KB Output is correct
12 Correct 55 ms 99232 KB Output is correct
13 Correct 52 ms 99288 KB Output is correct
14 Correct 50 ms 99020 KB Output is correct
15 Correct 53 ms 99484 KB Output is correct
16 Runtime error 144 ms 224052 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 94792 KB Output is correct
2 Correct 45 ms 94732 KB Output is correct
3 Correct 43 ms 94732 KB Output is correct
4 Runtime error 277 ms 226924 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -