제출 #1210755

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1210755		Younis_Dwai	Robot (JOI21_ho_t4)	C++20	0 / 100	255 ms	31708 KiB

Main

#pragma GCC optimize("O3,unroll-loops,Ofast")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#define endl "\n"
#define F first
#define S second
#define pb push_back
#define pf push_front
#define popf pop_frot
#define popb pop_back
#define int long long
#define in insert
#define mid (l+r)/2
//register int cnt
using namespace std;
const int N=1e5+5;
int n,m,tree[N*8],d[N],vis[N];
vector<pair<int,int>> adj[N];
vector<pair<int,pair<int,int>>> E[N];
void upd(int node , int l , int r , int id , int v){
     if(l==r){
         tree[node]+=v;
         return ;
     }
     else if(id<=mid) upd(node*2,l,mid,id,v);
     else upd(node*2+1,mid+1,r,id,v);
     tree[node]=min(tree[node*2],tree[node*2+1]);
     return ;
}
int query(int node , int l , int r  , int s , int e){
    if(l>=s && r<=e) return tree[node];
    else if(l>e || r<s) return 1e17;
    return min(query(node*2,l,mid,s,e),query(node*2+1,mid+1,r,s,e));
}
void dfs(int node){
     vis[node]=1;
     if(E[node].size()>1) return ;
     for(auto u : E[node]){
         if(vis[u.F]) continue ;
         dfs(u.F);
     }
     return ;
}
void Dijkstra(){
     for(int i=1;i<=n;i++) d[i]=1e18;
     d[1]=0;
     priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
     q.push({0,1});
     while(!q.empty()){
           int node=q.top().S,D=q.top().F;
           q.pop();
           if(vis[node]) continue ;
           vis[node]=1;
           for(auto u : adj[node]){
               if(d[u.F]>D+u.S){
                  d[u.F]=D+u.S;
                  q.push({d[u.F],u.F});
               }
           }
     }
     return;
}
int32_t main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(nullptr);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v,c,p;
        cin>>u>>v>>c>>p;
        E[u].pb({v,{c,p}});
        E[v].pb({u,{c,p}});
    }
    for(int i=1;i<=n;i++){
        for(auto u : E[i]){
            upd(1,1,m,u.S.F,u.S.S);
        }
        for(auto u : E[i]){
            adj[i].pb({u.F,min(u.S.S+tree[1],query(1,1,m,u.S.F,u.S.F)-u.S.S)});
        }
        for(auto u : E[i]){
            upd(1,1,m,u.S.F,-u.S.S);
        }
    }
    if(m==1){
       dfs(1);
       if(vis[n]) cout<<0;
       else cout<<-1;
    }
    else{
        Dijkstra();
        if(d[n]==1e18) cout<<-1;
        else cout<<d[n];
    }
    return 0;
}

• Subtask 1: 0 / 34
• Subtask 2: 0 / 24
• Subtask 3: 0 / 42