oj.uz

Submission #878494

# Submission time Handle Problem Language Result Execution time Memory
878494 2023-11-24T14:19:37 Z prohacker Passport (JOI23_passport) C++14
48 / 100
 2000 ms 70072 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pii pair<int,int>

using namespace std;

const int N = 2e5+10;
const int INF = INT_MAX;
const int mod = 1e9+7;
const string NAME = "solve";

int n,cnt;
int d[2][4*N];
vector<pii> adj[4*N];
int idx[4*N];
int q;

void build(int id = 1, int l = 1, int r = n) {
    if(l == r) {
        idx[id] = l;
        return;
    }
    idx[id] = ++cnt;
    int mid = l + r >> 1;
    build(id << 1,l,mid);
    build(id << 1 | 1,mid+1,r);
    adj[idx[id << 1]].push_back({idx[id],0});
    adj[idx[id << 1 | 1]].push_back({idx[id],0});
}

void update(int root, int u, int v, int id = 1, int l = 1, int r = n) {
    if(u <= l and r <= v) {
        adj[idx[id]].push_back({root,1});
        return;
    }
    int mid = l + r >> 1;
    if(u <= mid) {
        update(root,u,v,id << 1,l,mid);
    }
    if(mid+1 <= v) {
        update(root,u,v,id << 1 | 1,mid+1,r);
    }
}

queue<int> pq;

void dijkstra(int d[]) {
    while(!pq.empty()) {
        int u = pq.front();
        pq.pop();
        for(auto p:adj[u]) {
            int v = p.first;
            int w = p.second;
            if(d[u] + w < d[v]) {
                d[v] = d[u] + w;
                pq.push(v);
            }
        }
    }
}

signed main()
{
    if (fopen((NAME + ".inp").c_str(), "r")) {
        freopen((NAME + ".inp").c_str(), "r", stdin);
        freopen((NAME + ".out").c_str(), "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    cnt = n;
    build();
    for(int i = 1 ; i <= n ; i++) {
        int l,r; cin >> l >> r;
        update(i,l,r);
    }
    for(int j = 0 ; j < 2 ; j++) {
        for(int i = 1 ; i <= cnt ; i++) {
            d[j][i] = 1e8;
        }
    }
    d[0][1] = 0;
    pq.push(1);
    dijkstra(d[0]);
    d[1][n] = 0;
    pq.push(n);
    dijkstra(d[1]);
    for(int i = 1 ; i <= cnt ; i++) {
        d[0][i] = d[0][i] + d[1][i];
        if(1 < i and i < n) {
            d[0][i]--;
        }
        pq.push(i);
    }
    dijkstra(d[0]);
    cin >> q;
    while(q--) {
        int x; cin >> x;
        if(d[0][x] >= 1e8) {
            d[0][x] = -1;
        }
        cout << d[0][x] << '\n';
    }
    return 0;
}

Compilation message

passport.cpp: In function 'void build(int, int, int)':
passport.cpp:25:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   25 |     int mid = l + r >> 1;
      |               ~~^~~
passport.cpp: In function 'void update(int, int, int, int, int, int)':
passport.cpp:37:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |     int mid = l + r >> 1;
      |               ~~^~~
passport.cpp: In function 'int main()':
passport.cpp:66:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |         freopen((NAME + ".inp").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
passport.cpp:67:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |         freopen((NAME + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 22876 KB Output is correct
2 Correct 4 ms 22876 KB Output is correct
3 Correct 5 ms 22876 KB Output is correct
4 Correct 555 ms 70072 KB Output is correct
5 Execution timed out 2061 ms 47956 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 22876 KB Output is correct
2 Correct 5 ms 22876 KB Output is correct
3 Correct 4 ms 23000 KB Output is correct
4 Correct 4 ms 22984 KB Output is correct
5 Correct 4 ms 22992 KB Output is correct
6 Correct 6 ms 22876 KB Output is correct
7 Correct 4 ms 23128 KB Output is correct
8 Correct 5 ms 22872 KB Output is correct
9 Correct 5 ms 23132 KB Output is correct
10 Correct 4 ms 22876 KB Output is correct
11 Correct 4 ms 22876 KB Output is correct
12 Correct 4 ms 22876 KB Output is correct
13 Correct 5 ms 22876 KB Output is correct
14 Correct 5 ms 22872 KB Output is correct
15 Correct 5 ms 22876 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 22876 KB Output is correct
2 Correct 5 ms 22876 KB Output is correct
3 Correct 4 ms 23000 KB Output is correct
4 Correct 4 ms 22984 KB Output is correct
5 Correct 4 ms 22992 KB Output is correct
6 Correct 6 ms 22876 KB Output is correct
7 Correct 4 ms 23128 KB Output is correct
8 Correct 5 ms 22872 KB Output is correct
9 Correct 5 ms 23132 KB Output is correct
10 Correct 4 ms 22876 KB Output is correct
11 Correct 4 ms 22876 KB Output is correct
12 Correct 4 ms 22876 KB Output is correct
13 Correct 5 ms 22876 KB Output is correct
14 Correct 5 ms 22872 KB Output is correct
15 Correct 5 ms 22876 KB Output is correct
16 Correct 7 ms 23388 KB Output is correct
17 Correct 7 ms 23132 KB Output is correct
18 Correct 10 ms 23388 KB Output is correct
19 Correct 8 ms 23504 KB Output is correct
20 Correct 6 ms 23296 KB Output is correct
21 Correct 30 ms 23344 KB Output is correct
22 Correct 5 ms 23132 KB Output is correct
23 Correct 6 ms 23132 KB Output is correct
24 Correct 7 ms 23644 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 22876 KB Output is correct
2 Correct 5 ms 22876 KB Output is correct
3 Correct 4 ms 23000 KB Output is correct
4 Correct 4 ms 22984 KB Output is correct
5 Correct 4 ms 22992 KB Output is correct
6 Correct 6 ms 22876 KB Output is correct
7 Correct 4 ms 23128 KB Output is correct
8 Correct 5 ms 22872 KB Output is correct
9 Correct 5 ms 23132 KB Output is correct
10 Correct 4 ms 22876 KB Output is correct
11 Correct 4 ms 22876 KB Output is correct
12 Correct 4 ms 22876 KB Output is correct
13 Correct 5 ms 22876 KB Output is correct
14 Correct 5 ms 22872 KB Output is correct
15 Correct 5 ms 22876 KB Output is correct
16 Correct 7 ms 23388 KB Output is correct
17 Correct 7 ms 23132 KB Output is correct
18 Correct 10 ms 23388 KB Output is correct
19 Correct 8 ms 23504 KB Output is correct
20 Correct 6 ms 23296 KB Output is correct
21 Correct 30 ms 23344 KB Output is correct
22 Correct 5 ms 23132 KB Output is correct
23 Correct 6 ms 23132 KB Output is correct
24 Correct 7 ms 23644 KB Output is correct
25 Correct 4 ms 22876 KB Output is correct
26 Correct 4 ms 22876 KB Output is correct
27 Correct 7 ms 23388 KB Output is correct
28 Correct 7 ms 23328 KB Output is correct
29 Correct 6 ms 23132 KB Output is correct
30 Correct 30 ms 23232 KB Output is correct
31 Correct 7 ms 23132 KB Output is correct

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 22876 KB Output is correct
2 Correct 4 ms 22876 KB Output is correct
3 Correct 5 ms 22876 KB Output is correct
4 Correct 555 ms 70072 KB Output is correct
5 Execution timed out 2061 ms 47956 KB Time limit exceeded
6 Halted 0 ms 0 KB -