oj.uz

Submission #1086590

# Submission time Handle Problem Language Result Execution time Memory
1086590 2024-09-11T05:16:17 Z coldbr3w Passport (JOI23_passport) C++17
6 / 100
 1613 ms 348596 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<long long, long long>
#define pb push_back
#define F first
#define S second  
#define all(x) (x).begin(), (x).end()

const ll N = 6e5 + 100;
const ll inf = 1e17;
const ll mod = 1e9 + 7;
const ll block = 350;
vector<ll>adj[5 * N], rev[5 * N];
ll d[5 * N][2];
ll dp[5 * N];
ll n,q;
struct cmp{
    bool operator()(const pll &a, const pll &b){
        return a.S > b.S;
    }
};
void dijk(ll s, ll typ){
    priority_queue<pll, vector<pll>, cmp>q;
    for(int i = 1; i <= 9 * n;i++) d[i][typ] = inf;
    d[s][typ] = 0;
    q.push({s, d[s][typ]});
    while(q.size()){
        ll u = q.top().F, c = q.top().S; q.pop();
        if(c != d[u][typ]) continue;
        for(auto v : rev[u]){
            if(d[u][typ] + (v >= 8 * n + 1) < d[v][typ]){
                d[v][typ] = d[u][typ] + (v >= 8 * n + 1);
                q.push({v, d[v][typ]});
            }
        }
    }
}
void finalize(){
    priority_queue<pll, vector<pll>, cmp>q;
    for(int i = 1; i <= 9 * n;i++) dp[i] = d[i][0] + d[i][1], q.push({i, dp[i]});
    while(q.size()){
        ll u = q.top().F, c = q.top().S; q.pop();
        if(c != dp[u]) continue;
        for(auto v : rev[u]){
            if(dp[u] + (v >= 8 * n + 1) < dp[v]){
                dp[v] = dp[u] + (v >= 8 * n + 1);
                q.push({v, dp[v]});
            }
        }
    }
}
void build1(ll id, ll l, ll r){
    if(l == r){
        adj[id].pb(8 * n + l);
        adj[8 * n + l].pb(id);
		rev[id].pb(8 * n + l);
    	rev[8 * n + l].pb(id);
        return;
    }
    ll mid = (l + r) / 2;
    build1(2 * id, l, mid); build1(2 * id + 1, mid + 1, r);
    adj[id].pb(2 * id); adj[id].pb(2 * id + 1);
	rev[2 * id].pb(id); rev[2 * id + 1].pb(id);
}
void build2(ll id, ll l, ll r){
    if(l == r) {
        adj[4 * n + id].pb(8 * n + l);
        adj[8 * n + l].pb(4 * n + id);
        rev[8 * n + l].pb(4 * n + id);
        rev[4 * n + id].pb(8 * n + l);
        return;
    }
    ll mid = (l + r) / 2;
    build2(2 * id, l, mid); build2(2 * id + 1, mid + 1, r);
    adj[4 * n + 2 * id].pb(4 * n + id);
    rev[4 * n + id].pb(4 * n + 2 * id);
    adj[4 * n + 2 * id + 1].pb(4 * n + id);
    rev[4 * n + id].pb(4 * n + 2 * id + 1);
}
void add_edge2(ll id, ll l, ll r, ll left, ll right, ll v){ 
    if(l > right || r < left) return;
    if(left <= l && r <= right){
        adj[8 * n + v].pb(id);
        rev[id].pb(8 * n + v);
        return;
    }
    ll mid = (l + r) / 2;
    add_edge2(2 * id, l, mid, left, right, v);
    add_edge2(2 * id + 1, mid + 1, r, left, right, v);
}
void to_thic_cau(){
	cin >> n;
	build1(1,1,n); build2(1,1,n);
	for(int i = 1; i <= n;i++){
		ll l,r; cin >> l >> r;
		add_edge2(1,1,n,l,r,i);
	}
	dijk(8 * n + 1, 0); dijk(9 * n, 1); finalize();
    cin >> q;
    while(q--){
        ll x; cin >> x;
        cout << (dp[8 * n + x] >= inf ? -1 : dp[8 * n + x]) << "\n";
    }
}

signed main()   
{ 
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll tc = 1;
	//cin >> tc;
	while(tc--) to_thic_cau();
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 141156 KB Output is correct
2 Correct 65 ms 141140 KB Output is correct
3 Correct 59 ms 141136 KB Output is correct
4 Correct 1613 ms 348596 KB Output is correct
5 Correct 937 ms 305564 KB Output is correct
6 Correct 768 ms 297364 KB Output is correct
7 Correct 775 ms 286248 KB Output is correct
8 Correct 576 ms 294676 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 141140 KB Output is correct
2 Correct 59 ms 141136 KB Output is correct
3 Correct 60 ms 141140 KB Output is correct
4 Correct 56 ms 141140 KB Output is correct
5 Correct 61 ms 141152 KB Output is correct
6 Correct 60 ms 141140 KB Output is correct
7 Correct 62 ms 141368 KB Output is correct
8 Incorrect 61 ms 141244 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 141140 KB Output is correct
2 Correct 59 ms 141136 KB Output is correct
3 Correct 60 ms 141140 KB Output is correct
4 Correct 56 ms 141140 KB Output is correct
5 Correct 61 ms 141152 KB Output is correct
6 Correct 60 ms 141140 KB Output is correct
7 Correct 62 ms 141368 KB Output is correct
8 Incorrect 61 ms 141244 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 141140 KB Output is correct
2 Correct 59 ms 141136 KB Output is correct
3 Correct 60 ms 141140 KB Output is correct
4 Correct 56 ms 141140 KB Output is correct
5 Correct 61 ms 141152 KB Output is correct
6 Correct 60 ms 141140 KB Output is correct
7 Correct 62 ms 141368 KB Output is correct
8 Incorrect 61 ms 141244 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 141156 KB Output is correct
2 Correct 65 ms 141140 KB Output is correct
3 Correct 59 ms 141136 KB Output is correct
4 Correct 1613 ms 348596 KB Output is correct
5 Correct 937 ms 305564 KB Output is correct
6 Correct 768 ms 297364 KB Output is correct
7 Correct 775 ms 286248 KB Output is correct
8 Correct 576 ms 294676 KB Output is correct
9 Correct 60 ms 141140 KB Output is correct
10 Correct 59 ms 141136 KB Output is correct
11 Correct 60 ms 141140 KB Output is correct
12 Correct 56 ms 141140 KB Output is correct
13 Correct 61 ms 141152 KB Output is correct
14 Correct 60 ms 141140 KB Output is correct
15 Correct 62 ms 141368 KB Output is correct
16 Incorrect 61 ms 141244 KB Output isn't correct
17 Halted 0 ms 0 KB -