Submission #887449

#	Time	Username	Problem	Language	Result	Execution time	Memory
887449		guechotjrhh	Wild Boar (JOI18_wild_boar)	C++14	0 / 100	1 ms	448 KiB

wild_boar

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pi pair<int,int>
#define pli pair<ll,pair<pi,int>>
#define x first
#define y second

int n,m,t,l;
vector<ll> func(int N, int M, int T, int L, vector<int> A, vector<int> B, vector<int> C, vector<int> X, vector<int> P, vector<int> Q){
    n=N;m=M;t=T;l=L;
    vector<vector<pi>> g(n);
    for(int i=0;i<m;i++){
        --A[i];--B[i];
        g[A[i]].push_back({B[i],C[i]});
        g[B[i]].push_back({A[i],C[i]});
    }
    
    vector<vector<ll>> dist(n,vector<ll>(n,1e18)),dist1(n,vector<ll>(n,1e18));//reg dist, dist without the same start
    vector<vector<ll>> nxt(n,vector<ll>(n,-1)),nxt1(n,vector<ll>(n,-1));
    vector<vector<ll>> lst(n,vector<ll>(n,-1)),lst1(n,vector<ll>(n,-1));
    vector<vector<ll>> dist2(n,vector<ll>(n,1e18)),dist3(n,vector<ll>(n,1e18));//not the same end, not the same both
    vector<vector<ll>> nxt2(n,vector<ll>(n,-1)),nxt3(n,vector<ll>(n,-1));
    vector<vector<ll>> lst2(n,vector<ll>(n,-1)),lst3(n,vector<ll>(n,-1));
    for(int i=0;i<n;i++){
        dist[i][i] = 0;
        multiset<pli> st;
        for(int j=0;j<n;j++) st.insert({dist[i][j],{{j,-1},-1}});
        for(int j=0;j<n;j++) st.insert({dist1[i][j],{{j,-1},-1}});
        for(int j=0;j<n;j++) st.insert({dist2[i][j],{{j,-1},-1}});
        for(int j=0;j<n;j++) st.insert({dist3[i][j],{{j,-1},-1}});
        while(st.size()){
            pli pr = *st.begin(); st.erase(st.begin());
            for(pi &p : g[pr.y.x.x]){
                if(dist[i][p.x] > pr.x+p.y && pr.y.y!=p.x){
                    if(nxt[i][p.x] != pr.y.x.x){
                        st.erase(st.find({dist1[i][p.x],{{p.x,lst1[i][p.x]},nxt1[i][p.x]}}));
                        dist1[i][p.x] = dist[i][p.x];
                        nxt1[i][p.x]=nxt[i][p.x];
                        lst1[i][p.x]=lst[i][p.x];
                        st.insert({dist1[i][p.x],{{p.x,lst1[i][p.x]},nxt1[i][p.x]}});
                    }
                    if(lst[i][p.x] != (pr.y.x.x==i ? p.x : pr.y.x.y)){
                        st.erase(st.find({dist2[i][p.x],{{p.x,lst2[i][p.x]},nxt2[i][p.x]}}));
                        dist2[i][p.x] = dist[i][p.x];
                        nxt2[i][p.x]=nxt[i][p.x];
                        lst2[i][p.x]=lst[i][p.x];
                        st.insert({dist2[i][p.x],{{p.x,lst2[i][p.x]},nxt2[i][p.x]}});
                    }
                    if(lst[i][p.x] != (pr.y.x.x==i ? p.x : pr.y.x.y) && nxt[i][p.x] != pr.y.x.x){
                        st.erase(st.find({dist3[i][p.x],{{p.x,lst3[i][p.x]},nxt3[i][p.x]}}));
                        dist3[i][p.x] = dist[i][p.x];
                        nxt3[i][p.x]=nxt[i][p.x];
                        lst3[i][p.x]=lst[i][p.x];
                        st.insert({dist3[i][p.x],{{p.x,lst3[i][p.x]},nxt3[i][p.x]}});
                    }
                    st.erase(st.find({dist[i][p.x],{{p.x,lst[i][p.x]},nxt[i][p.x]}}));
                    dist[i][p.x] = pr.x+p.y;
                    nxt[i][p.x]=pr.y.x.x;
                    lst[i][p.x]= (pr.y.x.x==i) ? p.x : pr.y.x.y;
                    st.insert({dist[i][p.x],{{p.x,lst[i][p.x]},nxt[i][p.x]}});
                }
                if(dist1[i][p.x] > pr.x + p.y && nxt[i][p.x] != pr.y.x.x && pr.y.y != p.x){
                    st.erase(st.find({dist1[i][p.x],{{p.x,lst1[i][p.x]},nxt1[i][p.x]}}));
                    dist1[i][p.x] = pr.x+p.y;
                    nxt1[i][p.x]=pr.y.x.x;
                    lst1[i][p.x] = pr.y.x.x==i ? p.x : pr.y.x.y;
                    st.insert({dist1[i][p.x],{{p.x,lst1[i][p.x]},nxt1[i][p.x]}});
                }
                if(dist2[i][p.x] > pr.x + p.y && (lst[i][p.x] != (pr.y.x.x==i ? p.x : pr.y.x.y)) && pr.y.y != p.x){
                    st.erase(st.find({dist2[i][p.x],{{p.x,lst2[i][p.x]},nxt2[i][p.x]}}));
                    dist2[i][p.x] = pr.x+p.y;
                    nxt2[i][p.x]=pr.y.x.x;
                    lst2[i][p.x] = pr.y.x.x==i ? p.x : pr.y.x.y;
                    st.insert({dist2[i][p.x],{{p.x,lst2[i][p.x]},nxt2[i][p.x]}});
                }
                if(dist3[i][p.x] > pr.x + p.y && (lst[i][p.x] != (pr.y.x.x==i ? p.x : pr.y.x.y)) && nxt[i][p.x] != pr.y.x.x && pr.y.y != p.x){
                    st.erase(st.find({dist3[i][p.x],{{p.x,lst3[i][p.x]},nxt3[i][p.x]}}));
                    dist3[i][p.x] = pr.x+p.y;
                    nxt3[i][p.x]=pr.y.x.x;
                    lst3[i][p.x] = pr.y.x.x==i ? p.x : pr.y.x.y;
                    st.insert({dist3[i][p.x],{{p.x,lst3[i][p.x]},nxt3[i][p.x]}});
                }
            }
        }
    }
    
    /*for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cout<<i<<' '<<j<<endl;
            cout<<dist[i][j]<<' '<<nxt[i][j]<<' '<<lst[i][j]<<endl;
            cout<<dist1[i][j]<<' '<<nxt1[i][j]<<' '<<lst1[i][j]<<endl;
            cout<<dist2[i][j]<<' '<<nxt2[i][j]<<' '<<lst2[i][j]<<endl;
            cout<<dist3[i][j]<<' '<<nxt3[i][j]<<' '<<lst3[i][j]<<endl;
        }
    }*/
    
    vector<ll> res(t,-1);
    for(int i=0;i<l;i++) X[i]--;
    for(int i=0;i<t;i++){
        X[P[i]-1]=Q[i]-1;
        int lb = -1, ls = -1;
        ll rb = 0, rs = 0;
        for(int j=1;j<l;j++){
            vector<int> l; vector<ll> r;
            if(lb != nxt[X[j]][X[j-1]]){ r.push_back(rb+dist[X[j]][X[j-1]]); l.push_back(lst[X[j]][X[j-1]]); }
            if(lb != nxt1[X[j]][X[j-1]]){ r.push_back(rb+dist1[X[j]][X[j-1]]); l.push_back(lst1[X[j]][X[j-1]]); }
            if(lb != nxt2[X[j]][X[j-1]]){ r.push_back(rb+dist2[X[j]][X[j-1]]); l.push_back(lst2[X[j]][X[j-1]]); }
            if(lb != nxt3[X[j]][X[j-1]]){ r.push_back(rb+dist3[X[j]][X[j-1]]); l.push_back(lst3[X[j]][X[j-1]]); }
            if(rs<1e18 && ls != nxt[X[j]][X[j-1]]){ r.push_back(rs+dist[X[j]][X[j-1]]); l.push_back(lst[X[j]][X[j-1]]); }
            if(rs<1e18 && ls != nxt1[X[j]][X[j-1]]){ r.push_back(rs+dist1[X[j]][X[j-1]]); l.push_back(lst1[X[j]][X[j-1]]); }
            if(rs<1e18 && ls != nxt2[X[j]][X[j-1]]){ r.push_back(rs+dist2[X[j]][X[j-1]]); l.push_back(lst2[X[j]][X[j-1]]); }
            if(rs<1e18 && ls != nxt3[X[j]][X[j-1]]){ r.push_back(rs+dist3[X[j]][X[j-1]]); l.push_back(lst3[X[j]][X[j-1]]); }
            rb=rs=1e18; lb=ls=-1;
            for(int h=0;h<l.size();h++){
                if(r[h] < rb){
                    rb=r[h];
                    lb=l[h];
                }
            }
            for(int h=0;h<l.size();h++){
                if(r[h] < rs && l[h]!=lb){
                    rs=r[h];
                    ls=l[h];
                }
            }
            if(rb == 1e18){
                rb=-1;
                break;
            }
            //cout<<rb<<' '<<lb<<endl;
            //cout<<rs<<' '<<ls<<endl;
        }
        res[i]=rb;
    }
    
    return res;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int N,M,T,L; cin>>N>>M>>T>>L;
    vector<int> A(M),B(M),C(M);
    for(int i=0;i<M;i++) cin>>A[i]>>B[i]>>C[i];
    vector<int> X(L);
    for(int i=0;i<L;i++) cin>>X[i];
    vector<int> P(T),Q(T);
    for(int i=0;i<T;i++) cin>>P[i]>>Q[i];
    vector<ll> res = func(N,M,T,L,A,B,C,X,P,Q);
    for(ll i : res) cout<<i<<' '; cout<<endl;
}

Compilation message (stderr)

wild_boar.cpp: In function 'std::vector<long long int> func(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
wild_boar.cpp:115:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |             for(int h=0;h<l.size();h++){
      |                         ~^~~~~~~~~
wild_boar.cpp:121:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |             for(int h=0;h<l.size();h++){
      |                         ~^~~~~~~~~
wild_boar.cpp: In function 'int main()':
wild_boar.cpp:150:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  150 |     for(ll i : res) cout<<i<<' '; cout<<endl;
      |     ^~~
wild_boar.cpp:150:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  150 |     for(ll i : res) cout<<i<<' '; cout<<endl;
      |                                   ^~~~

• Subtask 1: 0 / 12
• Subtask 2: 0 / 35
• Subtask 3: 0 / 15
• Subtask 4: 0 / 38