Submission #880390

#	Time	Username	Problem	Language	Result	Execution time	Memory
880390		alicanyaz	Commuter Pass (JOI18_commuter_pass)	C++14	31 / 100	320 ms	36212 KiB

commuter_pass

#pragma GCC optimize("Ofast","unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ost;
#define endl "\n"
#define ll long long
#define ull unsigned long long
#define ld long double
#define pi pair<int,int> 
#define pll pair<long long,long long>
#define vi vector<int>
#define vll vector<long long>
#define vpi vector<pair<int,int>>
#define vpll vector<pair<long long,long long>>
#define vvi vector<vector<int>>
#define vvll vector<vector<long long>>
#define vr vector<range<int>>
#define cd complex<double>
#define pb push_back
void frd(string s){
    freopen((s+".in").c_str(),"r",stdin);
    freopen((s+".out").c_str(),"w",stdout);
}
template<typename T>
struct matrix{
    vector<T> mtx;
    T Tdef;
    int column=-1,row=-1;
    matrix()  {}
    matrix(int r,int c) {
        mtx.assign(r*c,Tdef);
        row = r;
        column = c;
    }
    matrix(int r,int c,T val){
        mtx.assign(r*c,val);
        row = r;
        column = c;
    }
    struct proxy{
        matrix *m ;
        int i;
        proxy(matrix* x , int y) : m(x) , i(y){}
        T &operator[] (int j){
            return (m->mtx[i*(m->row) + j]);
        }
    };
    proxy operator[](int i){
        return proxy(this,i);
    }
    void fill(T x){for(auto &y:mtx)y=x;}
    void fill_row(int rw,T x,int l=0,int r=-1){
        if(r==-1)r = column-1;
        for(int i=l;i<=r;i++){
            mtx[rw*row + i] = x;
        }
    }
    void fill_column(int cl,T x,int l=0,int r=-1){
        if(r == -1)r = row-1;
        for(int i=l;i<=r;i++){
            mtx[i*row + cl] = x;
        }
    }
    void inc_row(int rw,T x,int l=0,int r=-1){
        if(r==-1)r = column-1;
        for(int i=l;i<=r;i++){
            mtx[rw*row + i] += x;
        }
    }
    void inc_column(int cl,T x,int l=0,int r=-1){
        if(r == -1)r = row-1;
        for(int i=l;i<=r;i++){
            mtx[i*row + cl] +=x;
        }
    }
    int count(int rw,T x,int l=0,int r=-1){
        if(r == -1)r = column-1;
        int cnt = 0;
        for(int i=l;i<=r;i++)cnt += (mtx[rw*row + i] == x);
        return cnt;
    }
    
};
template<typename V,typename S> istream& operator >> (istream &x,pair<V,S> &p){cin >> p.first >> p.second ;return x;}
template<typename V,typename S> ostream& operator << (ostream &x,const pair<V,S> &p){cout << p.first <<" "<<p.second;return x;}
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define abs(x) ((x)>0?(x):-((x)))
#define fr(i,j) for(int i=0;i<j;i++)
#define frt(a,b,c) for(int a=b;a<c;a++)
#define fra(x,y) for(auto &x:y)
#define min(a,b) ((a)<(b)?(a):(b))
#define all(x) x.begin(),x.end()
int mlog(int x) {
    return 32 - __builtin_clz(x) - 1;
}
ll sum(ll a,ll b,ll M=1e+9+7){
    a%=M;b%=M;return (a+b)%M;
}
ll subs(ll a,ll b,ll M=1e+9+7){
    a-=b;a%=M;if(a<0)a+=M;return a;
}
ll mult(ll a,ll b,ll M=1e+9+7){
    a%=M;b%=M;return (a*b)%M;
}
ll bp(ll a,ll b,ll M=1e+9+7){
    if(b == 0)return 1;
    if(b == 1)return a;
    ll x = bp(a,b/2,M);
    x = mult(x,x,M);
    if(b%2)x=mult(x,a,M);
    return x;
}
#define int ll
#define MAXN 200005
const ll INF = 1e+16 + 2323231;
vector<vpi> adj;
array<int,MAXN> vis;
array<ll,MAXN> U_dj , V_dj , S_dj , UDP , VDP , DP;
//vll U_dj , V_dj ,  S_dj;
vvll sp;

void djikstra(array<ll,MAXN> &A,int st){
    A[st] = 0;
    set<pll> sst;sst.insert({0,st});
    while(sst.size()){
        auto it = *(sst.begin());
        sst.erase(sst.begin());
        for(auto &x:adj[it.second]){
            if(A[x.first] > A[it.second] + x.second){
                sst.erase({A[x.first],x.first});
                A[x.first] = A[it.second] + x.second;
                sst.insert({A[x.first],x.first});
            }
        }
    }
}
ll ans;
void DFS(int V){
    vis[V] = 1;
    fra(x,sp[V]){
        if(vis[x] == 0)DFS(x);
    }
    VDP[V] = INF;
    UDP[V] = INF;
    fra(x,sp[V]){
        if(min(V_dj[V] , VDP[x]) + min(U_dj[V] , UDP[x])  < VDP[V] + UDP[V]){
            VDP[V] = min(V_dj[V] , VDP[x]);
            UDP[V] = min(U_dj[V] , UDP[x]);
        }
    }
    vis[V] = 1;
}
vi TYPE;
void DFS2(int V,int S){
    vis[V] = 1;
    if(V == S){
        TYPE[V] = 1;return;
    }
    fra(x,sp[V]){
        if(vis[x] == 0)DFS2(x,S);
        if(TYPE[x] == 1)TYPE[V] = 1;
    }
    if(TYPE[V])V_dj[V] = 0;
}
int32_t main(){
    fastio;
    int N,M;cin>>N>>M;TYPE.assign(N,0);
    adj.assign(N,vpi(0));sp.assign(N,vll(0));
    fill(all(vis),0);fill(all(U_dj),INF);fill(all(V_dj),INF);fill(all(S_dj),INF);fill(all(VDP),INF);fill(all(UDP),INF);fill(all(DP),INF);
    int S,T,V,U;cin>>S>>T>>V>>U;S--;T--;V--;U--;
    fr(i,M){
        int a,b;ll c;cin>>a>>b>>c;a--;b--;
        adj[a].pb({b,c});
        adj[b].pb({a,c});
    }
    djikstra(U_dj,U);
    djikstra(V_dj,V);
    
    S_dj[S] = 0;
    set<pll> sst;sst.insert({0,S});
    while (sst.size()){
        auto it = *(sst.begin());
        sst.erase(sst.begin());
        for(auto &x:adj[it.second]){
            if(S_dj[x.first] == S_dj[it.second] + x.second)
                sp[x.first].pb(it.second);
            else if(S_dj[x.first] > S_dj[it.second] + x.second){
                sp[x.first].clear();
                sst.erase({S_dj[x.first],x.first});
                S_dj[x.first] = S_dj[it.second] + x.second;
                sst.insert({S_dj[x.first],x.first});
                sp[x.first].pb(it.second); 
            }
        }
    }
    if(V == S)DFS2(T,S);
    fill(all(vis),0);   
    ans = V_dj[U];
    DFS(T);
    cout << min(ans,VDP[T] + UDP[T]) << endl;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void frd(std::string)':
commuter_pass.cpp:25:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |     freopen((s+".in").c_str(),"r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:26:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     freopen((s+".out").c_str(),"w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 16 / 16
• Subtask 2: 15 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 45