oj.uz

Submission #736888

# Submission time Handle Problem Language Result Execution time Memory
736888 2023-05-06T10:13:48 Z Cookie Passport (JOI23_passport) C++14
16 / 100
 135 ms 225996 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<pii>adj[2000 * 2000 + 1];
int id(int i, int j){
    return((i - 1) * n + j);
}
void add_edge(int a, int b, int c, int d, int w){
    adj[id(c, d)].pb({id(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[id(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[id(1, n)] = 0;
    deque<int>dq; dq.pb({id(1, n)});
    while(!dq.empty()){
        auto u = dq.front(); dq.pop_front();
        for(auto [v, w]: adj[u]){
            if(d[v] > d[u] + w){
                d[v] = d[u] + w;
                if(w){
                    dq.pb(v);
                }else{
                    dq.push_front(v);
                }
            }
        }
    }
    cin >> q;
    forr(i, 0, q){
        int x; cin >> x;
        int val = id(x, x);
        if(d[val] == 1e9)cout << -1 << "\n";
        else cout << d[val] << "\n";
    }
    return(0);
}

Compilation message

passport.cpp: In function 'int main()':
passport.cpp:66:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   66 |         for(auto [v, w]: adj[u]){
      |                  ^

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 94156 KB Output is correct
2 Correct 43 ms 94148 KB Output is correct
3 Correct 46 ms 94156 KB Output is correct
4 Runtime error 134 ms 225996 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 43 ms 94236 KB Output is correct
2 Correct 44 ms 94268 KB Output is correct
3 Correct 43 ms 94216 KB Output is correct
4 Correct 44 ms 94156 KB Output is correct
5 Correct 47 ms 94156 KB Output is correct
6 Correct 43 ms 94156 KB Output is correct
7 Correct 43 ms 94156 KB Output is correct
8 Correct 43 ms 94216 KB Output is correct
9 Correct 49 ms 94156 KB Output is correct
10 Correct 44 ms 94156 KB Output is correct
11 Correct 50 ms 96844 KB Output is correct
12 Correct 50 ms 96980 KB Output is correct
13 Correct 51 ms 97164 KB Output is correct
14 Correct 48 ms 96904 KB Output is correct
15 Correct 51 ms 97064 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 94236 KB Output is correct
2 Correct 44 ms 94268 KB Output is correct
3 Correct 43 ms 94216 KB Output is correct
4 Correct 44 ms 94156 KB Output is correct
5 Correct 47 ms 94156 KB Output is correct
6 Correct 43 ms 94156 KB Output is correct
7 Correct 43 ms 94156 KB Output is correct
8 Correct 43 ms 94216 KB Output is correct
9 Correct 49 ms 94156 KB Output is correct
10 Correct 44 ms 94156 KB Output is correct
11 Correct 50 ms 96844 KB Output is correct
12 Correct 50 ms 96980 KB Output is correct
13 Correct 51 ms 97164 KB Output is correct
14 Correct 48 ms 96904 KB Output is correct
15 Correct 51 ms 97064 KB Output is correct
16 Runtime error 135 ms 222948 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 43 ms 94236 KB Output is correct
2 Correct 44 ms 94268 KB Output is correct
3 Correct 43 ms 94216 KB Output is correct
4 Correct 44 ms 94156 KB Output is correct
5 Correct 47 ms 94156 KB Output is correct
6 Correct 43 ms 94156 KB Output is correct
7 Correct 43 ms 94156 KB Output is correct
8 Correct 43 ms 94216 KB Output is correct
9 Correct 49 ms 94156 KB Output is correct
10 Correct 44 ms 94156 KB Output is correct
11 Correct 50 ms 96844 KB Output is correct
12 Correct 50 ms 96980 KB Output is correct
13 Correct 51 ms 97164 KB Output is correct
14 Correct 48 ms 96904 KB Output is correct
15 Correct 51 ms 97064 KB Output is correct
16 Runtime error 135 ms 222948 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 43 ms 94156 KB Output is correct
2 Correct 43 ms 94148 KB Output is correct
3 Correct 46 ms 94156 KB Output is correct
4 Runtime error 134 ms 225996 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -