oj.uz

Submission #1097350

# Submission time Handle Problem Language Result Execution time Memory
1097350 2024-10-07T01:49:14 Z vjudge1 Passport (JOI23_passport) C++17
0 / 100
 199 ms 65028 KB 
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

const int INF = 1e9+7;
const int MAXN = 2e5+3;

int n, q, x;

vector<pair<int,int>> e[4*MAXN];

int ans;
int f[4*MAXN];
int ID[MAXN];
bool vis[4*MAXN];

void STbuild(int idx=1, int l=1, int r=n){
    if(l==r){
        ID[l] = idx;
        return;
    }
    int mid = l+r>>1;
    e[idx].push_back({idx<<1, 0});
    e[idx].push_back({idx<<1|1, 0});
    STbuild(idx<<1, l, mid);
    STbuild(idx<<1|1, mid+1, r);
}

void STunion(int z, int u, int v, int idx=1, int l=1, int r=n){
    if(v<l || r<u)return;
    if(u<=l && r<=v){
        if(idx==ID[z])return;
        e[ID[z]].push_back({idx, 1});
        return;
    }
    int mid = l+r>>1;
    STunion(z,u,v,idx<<1,l,mid);
    STunion(z,u,v,idx<<1|1,mid+1,r);
}


// class Compare{
// public: bool operator()(const int &a, const int &b){
//     return f[a] > f[b];
// }};
// priority_queue<int, vector<int>, Compare> pq;
queue<int> pq;

void solve(){
    for(int i=1; i<=4*n; ++i) f[i] = INF, vis[i] = 0;

    pq.push(ID[x]);
    f[ID[x]] = 0;
    vis[ID[x]] = 1;

    while(!pq.empty()){
        int u = pq.front(); pq.pop();
        for(pair<int,int> &z : e[u]){
            int v = z.first,
                w = z.second;
            if(vis[v])continue;

            pq.push(v);
            vis[v] = 1;
            f[v] = min(f[v],f[u]+w);
        }
    }
    
    ans = 0;
    for(int i=1; i<=n; ++i)ans=max(ans,f[ID[i]]);
    cout << (ans>=INF ? -1 : ans) << '\n';
}



signed main()
{
    cin.tie(0) -> sync_with_stdio(0);
    
    cin >> n;
    STbuild();
    for(int l, r, i=1; i<=n; ++i){
        cin >> l >> r;
        STunion(i, l, r);
    }
    cin >> q;
    while(q--){
        cin >> x;
        solve();
    }

    return 0;
}

Compilation message

passport.cpp: In function 'void STbuild(int, int, int)':
passport.cpp:25:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   25 |     int mid = l+r>>1;
      |               ~^~
passport.cpp: In function 'void STunion(int, int, int, int, int, int)':
passport.cpp:39:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |     int mid = l+r>>1;
      |               ~^~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19032 KB Output is correct
2 Correct 9 ms 19156 KB Output is correct
3 Correct 9 ms 19036 KB Output is correct
4 Incorrect 199 ms 65028 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19036 KB Output is correct
2 Correct 8 ms 19252 KB Output is correct
3 Correct 9 ms 19248 KB Output is correct
4 Correct 9 ms 19032 KB Output is correct
5 Correct 8 ms 19036 KB Output is correct
6 Correct 9 ms 19060 KB Output is correct
7 Incorrect 9 ms 19036 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19036 KB Output is correct
2 Correct 8 ms 19252 KB Output is correct
3 Correct 9 ms 19248 KB Output is correct
4 Correct 9 ms 19032 KB Output is correct
5 Correct 8 ms 19036 KB Output is correct
6 Correct 9 ms 19060 KB Output is correct
7 Incorrect 9 ms 19036 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19036 KB Output is correct
2 Correct 8 ms 19252 KB Output is correct
3 Correct 9 ms 19248 KB Output is correct
4 Correct 9 ms 19032 KB Output is correct
5 Correct 8 ms 19036 KB Output is correct
6 Correct 9 ms 19060 KB Output is correct
7 Incorrect 9 ms 19036 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19032 KB Output is correct
2 Correct 9 ms 19156 KB Output is correct
3 Correct 9 ms 19036 KB Output is correct
4 Incorrect 199 ms 65028 KB Output isn't correct
5 Halted 0 ms 0 KB -