oj.uz

Submission #889413

# Submission time Handle Problem Language Result Execution time Memory
889413 2023-12-19T16:00:42 Z guechotjrhh Wild Boar (JOI18_wild_boar) C++14
0 / 100
 1 ms 348 KB 
#include<vector>
#include<set>
#include<iostream>
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<int>> nxt(n,vector<int>(n,-1)),nxt1(n,vector<int>(n,-1));
    vector<vector<int>> lst(n,vector<int>(n,-1)),lst1(n,vector<int>(n,-1));
    vector<vector<ll>> dist2(n,vector<ll>(n,1e18)),dist3(n,vector<ll>(n,1e18));//not the same end, (not the same start of 0, and not the same end of 1)
    vector<vector<int>> nxt2(n,vector<int>(n,-1)),nxt3(n,vector<int>(n,-1));
    vector<vector<int>> lst2(n,vector<int>(n,-1)),lst3(n,vector<int>(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){
                        if (lst1[i][p.x] != lst[i][p.x]) {
                            st.erase(st.find({ dist3[i][p.x],{{p.x,lst3[i][p.x]},nxt3[i][p.x]} }));
                            dist3[i][p.x] = dist1[i][p.x];
                            nxt3[i][p.x] = nxt1[i][p.x];
                            lst3[i][p.x] = lst1[i][p.x];
                            st.insert({ dist3[i][p.x],{{p.x,lst3[i][p.x]},nxt3[i][p.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(lst1[i][p.x] != lst[i][p.x] && 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){
                    if (lst1[i][p.x] != pr.y.x.x == i ? p.x : pr.y.x.y) {
                        st.erase(st.find({ dist3[i][p.x],{{p.x,lst3[i][p.x]},nxt3[i][p.x]} }));
                        dist3[i][p.x] = dist1[i][p.x];
                        nxt3[i][p.x] = nxt1[i][p.x];
                        lst3[i][p.x] = lst1[i][p.x];
                        st.insert({ dist3[i][p.x],{{p.x,lst3[i][p.x]},nxt3[i][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 && (lst1[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;
}
 /*
5 6 1 5
1 2 8
1 3 8
1 4 8
2 5 2
3 4 6
4 5 6
2
5
1
5
3
5 2

 */
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

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:73:38: warning: suggest parentheses around comparison in operand of '==' [-Wparentheses]
   73 |                     if (lst1[i][p.x] != pr.y.x.x == i ? p.x : pr.y.x.y) {
wild_boar.cpp:131:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |             for(int h=0;h<l.size();h++){
      |                         ~^~~~~~~~~
wild_boar.cpp:137:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |             for(int h=0;h<l.size();h++){
      |                         ~^~~~~~~~~
wild_boar.cpp: In function 'int main()':
wild_boar.cpp:181:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  181 |     for(ll i : res) cout<<i<<' '; cout<<endl;
      |     ^~~
wild_boar.cpp:181:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  181 |     for(ll i : res) cout<<i<<' '; cout<<endl;
      |                                   ^~~~

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 1 ms 344 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 1 ms 344 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 1 ms 344 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 1 ms 344 KB Output isn't correct
10 Halted 0 ms 0 KB -