Submission #1278647

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278647		sasde	Passport (JOI23_passport)	C++20	100 / 100	378 ms	81944 KiB

passport

#include<bits/stdc++.h>
using namespace std;
bool M1;
#define PI 3.14159265358979323846
#define sz(a) (int)a.size()
#define all(x) x.begin(),x.end()
#define ii pair<int,int>
#define iii pair<int,ii>
#define iv pair<ii,ii>
#define se second
#define fi first
#define ffi fi.fi
#define sfi se.fi
#define sse se.se
#define fse fi.se
#define lt(i, c, d) for(int i = c; i <= d; ++i)
#define fl(i, c, d) for(int i = d; i >= c; --i)
#define pb push_back
#define emb emplace_back
#define emf emplace_front
#define em emplace
#define look_memory cerr<<abs(&M2-&M1)/1024.0/1024<<'\n'
#define look_time   cerr << "TIME : " << clock() * 0.001 << "s" <<'\n'
const int N=1e6+5,lg=30,mod=1e9+7,inf=1e9;
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int u,int v){
 return u+rd()%(v-u+1);
}
int dx[]={1,0,-1,0,1,1,-1,-1};
int dy[]={0,-1,0,1,1,-1,1,-1};
struct pt{
    int l,r,i;
}a[N];
int node,ans[N],val[N];
vector<ii>ver[N];

struct segmax {
    int n;
    vector<int> st, lazy;
    segmax() {};
    segmax(int _n): n(_n), st(n * 4 + 5, 0), lazy(n * 4 + 5, 0) {};

    void build(int id, int l, int r) {
        if (l == r) {
            val[l]=id;
            return;
        }
        int mid = (l + r) >> 1;
        build(id << 1, l, mid);
        build(id << 1 | 1, mid + 1, r);
        ver[id<<1|1].emb(id,0);
        ver[id<<1].emb(id,0);
    }
    void update(int id, int l, int r, int u,int v, int value) {
        if (u>r||v<l) return;
        if (u<=l&&r<=v) {
            ver[id].emb(value,1);
            return;
        }
        int mid = (l + r) >> 1;
        update(id << 1, l, mid, u,v, value);
        update(id << 1 | 1, mid + 1, r, u,v, value);
    }
};
int dist[N][2];
void bfs(int t){
    for(int i=1;i<=node*4;++i)dist[i][t]=inf;
    dist[val[t==0?1:node]][t]=0;
    deque<int>p;
    p.emf(val[t==0?1:node]);
    while(!p.empty()){
        int u=p.front();
        // cout <<u<<" "<<t<<'\n';
        p.pop_front();
        for(auto x:ver[u]){
            if(dist[x.fi][t]>dist[u][t]+x.se){
                dist[x.fi][t]=dist[u][t]+x.se;
                if(x.se==0)
                    p.emf(x.fi);
                else p.emb(x.fi);
            }
        }
    }
}
void dijk(){
    for(int i=1;i<=node*4;++i)ans[i]=inf;
        priority_queue<ii,vector<ii>,greater<ii>>p;
    for(int i=1;i<=node;++i){
        ans[val[i]]=dist[val[i]][0]+dist[val[i]][1]-(i!=1&&i!=node);
        p.em(ans[val[i]],val[i]);
    }
    while(!p.empty()){
        ii x=p.top();
        // cout <<x.fi<<" "<<x.se<<'\n';
        p.pop();
        if(x.fi!=ans[x.se])continue;
        for(auto v:ver[x.se]){
            if(ans[v.fi]>x.fi+v.se){
                ans[v.fi]=x.fi+v.se;
                p.em(ans[v.fi],v.fi);
            }
        }
    }
}
bool M2;
void solve(){
    cin >> node;
    segmax seg(node);
    seg.build(1,1,node);
    for(int i=1;i<=node;++i){
        cin >> a[i].l >> a[i].r;
        a[i].i=i;
        seg.update(1,1,node,a[i].l,a[i].r,val[i]);
        // cout << a[i].l<<" "<<a[i].r<<'\n';
    }
    bfs(0);
    bfs(1);
    dijk();
    int query;
    cin >> query;
    while(query--){
        int x;
        cin >> x;
        if(ans[val[x]]>=node)ans[val[x]]=-1;
        cout << ans[val[x]]<<'\n';
    }
    // cout <<1;
}
main()
{
  srand(time(0));
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    #define task "aws"
    if(fopen(task".inp","r")){
      freopen(task".inp","r",stdin);
      freopen(task".out","w",stdout);
    }
    int t=1;
 //   cin >> t;
while(t--){
    solve();
}
look_memory;
look_time;
}

Compilation message (stderr)

passport.cpp:129:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  129 | main()
      | ^~~~
passport.cpp: In function 'int main()':
passport.cpp:137:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  137 |       freopen(task".inp","r",stdin);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
passport.cpp:138:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  138 |       freopen(task".out","w",stdout);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 8 / 8
• Subtask 5: 46 / 46