oj.uz

Submission #892076

# Submission time Handle Problem Language Result Execution time Memory
892076 2023-12-24T18:34:22 Z guechotjrhh Wild Boar (JOI18_wild_boar) C++14
0 / 100
 1 ms 456 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));//start unlike 0, end unlike 1
    vector<vector<int>> nxt2(n,vector<int>(n,-1)),nxt3(n,vector<int>(n,-1));//start unlike 1, end unlike 0
    vector<vector<int>> lst2(n,vector<int>(n,-1)),lst3(n,vector<int>(n,-1));
    vector<vector<ll>> dist4(n, vector<ll>(n, 1e18));//start not same of 2, end not same of 0
    vector<vector<int>> nxt4(n, vector<int>(n, -1));
    vector<vector<int>> lst4(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} });
        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) {
                    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]} });
                }
            }
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (pi& p : g[j]) {
                if (dist1[i][p.x] > dist[i][j] + p.y && j != nxt[i][p.x] && nxt[i][j] != p.x) {
                    dist1[i][p.x] = dist[i][j] + p.y;
                    nxt1[i][p.x] = j;
                    lst1[i][p.x] = (i == j ? p.x : lst[i][j]);
                }
            }
        }
        multiset<pli> st;
        for (int j = 0; j < n; j++) st.insert({ dist1[i][j],{{j,lst1[i][j]},nxt1[i][j]}});
        while (st.size()) {
            pli pr = *st.begin(); st.erase(st.begin());
            for (pi& p : g[pr.y.x.x]) {
                if (dist1[i][p.x] > pr.x + p.y && pr.y.y != p.x && 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] = 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]} });
                }
            }
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (pi& p : g[j]) {
                if (dist2[i][p.x] > dist[i][j] + p.y && j != nxt[i][p.x] && (i==j ? p.x : lst[i][j]) != lst1[i][p.x] && nxt[i][j] != p.x) {
                    dist2[i][p.x] = dist[i][j] + p.y;
                    nxt2[i][p.x] = j;
                    lst2[i][p.x] = (i == j ? p.x : lst[i][j]);
                }
            }
        }
        for (int j = 0; j < n; j++) {
            for (pi& p : g[j]) {
                if (dist2[i][p.x] > dist1[i][j] + p.y && j != nxt[i][p.x] && lst1[i][j] != lst1[i][p.x] && nxt1[i][j] != p.x) {
                    dist2[i][p.x] = dist1[i][j] + p.y;
                    nxt2[i][p.x] = j;
                    lst2[i][p.x] = lst1[i][j];
                }
            }
        }
        multiset<pli> st;
        for (int j = 0; j < n; j++) st.insert({ dist2[i][j],{{j,lst2[i][j]},nxt2[i][j]} });
        while (st.size()) {
            pli pr = *st.begin(); st.erase(st.begin());
            for (pi& p : g[pr.y.x.x]) {
                if (dist2[i][p.x] > pr.x + p.y && pr.y.y != p.x && nxt[i][p.x] != pr.y.x.x && ((pr.y.x.x == i) ? p.x : pr.y.x.y) != lst1[i][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]} });
                }
            }
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (pi& p : g[j]) {
                if (dist3[i][p.x] > dist[i][j] + p.y && j != nxt1[i][p.x] && (i == j ? p.x : lst[i][j]) != lst[i][p.x] && nxt[i][j] != p.x) {
                    dist3[i][p.x] = dist[i][j] + p.y;
                    nxt3[i][p.x] = j;
                    lst3[i][p.x] = (i == j ? p.x : lst[i][j]);
                }
            }
        }
        for (int j = 0; j < n; j++) {
            for (pi& p : g[j]) {
                if (dist3[i][p.x] > dist1[i][j] + p.y && j != nxt1[i][p.x] && lst1[i][j] != lst[i][p.x] && nxt1[i][j] != p.x) {
                    dist3[i][p.x] = dist1[i][j] + p.y;
                    nxt3[i][p.x] = j;
                    lst3[i][p.x] = lst1[i][j];
                }
            }
        }
        multiset<pli> st;
        for (int j = 0; j < n; j++) st.insert({ dist3[i][j],{{j,lst3[i][j]},nxt3[i][j]} });
        while (st.size()) {
            pli pr = *st.begin(); st.erase(st.begin());
            for (pi& p : g[pr.y.x.x]) {
                if (dist3[i][p.x] > pr.x + p.y && pr.y.y != p.x && nxt1[i][p.x] != pr.y.x.x && ((pr.y.x.x == i) ? p.x : pr.y.x.y) != 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] = 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++) {
            for (pi& p : g[j]) {
                if (dist4[i][p.x] > dist[i][j] + p.y && j != nxt2[i][p.x] && (i == j ? p.x : lst[i][j]) != lst[i][p.x] && nxt[i][j] != p.x) {
                    dist4[i][p.x] = dist[i][j] + p.y;
                    nxt4[i][p.x] = j;
                    lst4[i][p.x] = (i == j ? p.x : lst[i][j]);
                }
            }
        }
        for (int j = 0; j < n; j++) {
            for (pi& p : g[j]) {
                if (dist4[i][p.x] > dist2[i][j] + p.y && j != nxt2[i][p.x] && lst2[i][j] != lst[i][p.x] && nxt2[i][j] != p.x) {
                    dist4[i][p.x] = dist2[i][j] + p.y;
                    nxt4[i][p.x] = j;
                    lst4[i][p.x] = lst2[i][j];
                }
            }
        }
        multiset<pli> st;
        for (int j = 0; j < n; j++) st.insert({ dist4[i][j],{{j,lst4[i][j]},nxt4[i][j]} });
        while (st.size()) {
            pli pr = *st.begin(); st.erase(st.begin());
            for (pi& p : g[pr.y.x.x]) {
                if (dist4[i][p.x] > pr.x + p.y && pr.y.y != p.x && nxt2[i][p.x] != pr.y.x.x && ((pr.y.x.x == i) ? p.x : pr.y.x.y) != lst[i][p.x]) {
                    st.erase(st.find({ dist4[i][p.x],{{p.x,lst4[i][p.x]},nxt4[i][p.x]} }));
                    dist4[i][p.x] = pr.x + p.y;
                    nxt4[i][p.x] = pr.y.x.x;
                    lst4[i][p.x] = (pr.y.x.x == i) ? p.x : pr.y.x.y;
                    st.insert({ dist4[i][p.x],{{p.x,lst4[i][p.x]},nxt4[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;
            cout<<dist4[i][j]<<' '<<nxt4[i][j]<<' '<<lst4[i][j]<<endl;
        }
    }*/
    
    vector<ll> res(t,-1);
    for(int i=0;i<l;i++) X[i]--;
    for(int d=0;d<t;d++){
        X[P[d]-1]=Q[d]-1;
        int lb = -1, ls = -1;
        ll rb = 0, rs = 0;
        for(int q=1;q<l;q++){
            //cout << X[q - 1] << " -> " << X[q] << endl;
            
            int i = X[q], j = X[q - 1];

            ll nrb=1e18, nrs=1e18;
            int nlb, nls=-1;

            if (lb != nxt[i][j] && rb + dist[i][j] < nrb && nxt[i][j] != -1 && lst[i][j] != -1) { nrb = rb + dist[i][j]; nlb = lst[i][j]; }
            if (lb != nxt1[i][j] && rb + dist1[i][j] < nrb && nxt1[i][j] != -1 && lst1[i][j] != -1) { nrb = rb + dist1[i][j]; nlb = lst1[i][j]; }
            if (lb != nxt2[i][j] && rb + dist2[i][j] < nrb && nxt2[i][j] != -1 && lst2[i][j] != -1) { nrb = rb + dist2[i][j]; nlb = lst2[i][j]; }
            if (lb != nxt3[i][j] && rb + dist3[i][j] < nrb && nxt3[i][j] != -1 && lst3[i][j] != -1) { nrb = rb + dist3[i][j]; nlb = lst3[i][j]; }
            if (lb != nxt4[i][j] && rb + dist4[i][j] < nrb && nxt4[i][j] != -1 && lst4[i][j] != -1) { nrb = rb + dist4[i][j]; nlb = lst4[i][j]; }
            if (ls != nxt[i][j] && rs + dist[i][j] < nrb && nxt[i][j] != -1 && lst[i][j] != -1) { nrb = rs + dist[i][j]; nlb = lst[i][j]; }
            if (ls != nxt1[i][j] && rs + dist1[i][j] < nrb && nxt1[i][j] != -1 && lst1[i][j] != -1) { nrb = rs + dist1[i][j]; nlb = lst1[i][j]; }
            if (ls != nxt2[i][j] && rs + dist2[i][j] < nrb && nxt2[i][j] != -1 && lst2[i][j] != -1) { nrb = rs + dist2[i][j]; nlb = lst2[i][j]; }
            if (ls != nxt3[i][j] && rs + dist3[i][j] < nrb && nxt3[i][j] != -1 && lst3[i][j] != -1) { nrb = rs + dist3[i][j]; nlb = lst3[i][j]; }
            if (ls != nxt4[i][j] && rs + dist4[i][j] < nrb && nxt4[i][j] != -1 && lst4[i][j] != -1) { nrb = rs + dist4[i][j]; nlb = lst4[i][j]; }

            if (lb != nxt[i][j] && rb + dist[i][j] < nrs && lst[i][j] != nlb && nxt[i][j] != -1 && lst[i][j] != -1) { nrs = rb + dist[i][j]; nls = lst[i][j]; }
            if (lb != nxt1[i][j] && rb + dist1[i][j] < nrs && lst1[i][j] != nlb && nxt1[i][j] != -1 && lst1[i][j] != -1) { nrs = rb + dist1[i][j]; nls = lst1[i][j]; }
            if (lb != nxt2[i][j] && rb + dist2[i][j] < nrs && lst2[i][j] != nlb && nxt2[i][j] != -1 && lst2[i][j] != -1) { nrs = rb + dist2[i][j]; nls = lst2[i][j]; }
            if (lb != nxt3[i][j] && rb + dist3[i][j] < nrs && lst3[i][j] != nlb && nxt3[i][j] != -1 && lst3[i][j] != -1) { nrs = rb + dist3[i][j]; nls = lst3[i][j]; }
            if (lb != nxt4[i][j] && rb + dist4[i][j] < nrs && lst4[i][j] != nlb && nxt4[i][j] != -1 && lst4[i][j] != -1) { nrs = rb + dist4[i][j]; nls = lst4[i][j]; }
            if (ls != nxt[i][j] && rs + dist[i][j] < nrs && lst[i][j] != nlb && nxt[i][j] != -1 && lst[i][j] != -1) { nrs = rs + dist[i][j]; nls = lst[i][j]; }
            if (ls != nxt1[i][j] && rs + dist1[i][j] < nrs && lst1[i][j] != nlb && nxt1[i][j] != -1 && lst1[i][j] != -1) { nrs = rs + dist1[i][j]; nls = lst1[i][j]; }
            if (ls != nxt2[i][j] && rs + dist2[i][j] < nrs && lst2[i][j] != nlb && nxt2[i][j] != -1 && lst2[i][j] != -1) { nrs = rs + dist2[i][j]; nls = lst2[i][j]; }
            if (ls != nxt3[i][j] && rs + dist3[i][j] < nrs && lst3[i][j] != nlb && nxt3[i][j] != -1 && lst3[i][j] != -1) { nrs = rs + dist3[i][j]; nls = lst3[i][j]; }
            if (ls != nxt4[i][j] && rs + dist4[i][j] < nrs && lst4[i][j] != nlb && nxt4[i][j] != -1 && lst4[i][j] != -1) { nrs = rs + dist4[i][j]; nls = lst4[i][j]; }


            rb = nrb; rs = nrs; lb = nlb; ls = nls;
            if(rb >= 1e18){
                rb=-1;
                break;
            }
            //cout<<rb<<' '<<lb<<endl;
            //cout<<rs<<' '<<ls<<endl<<endl;
        }
        res[d]=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 'int main()':
wild_boar.cpp:262:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  262 |     for(ll i : res) cout<<i<<' '; cout<<endl;
      |     ^~~
wild_boar.cpp:262:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  262 |     for(ll i : res) cout<<i<<' '; cout<<endl;
      |                                   ^~~~
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:220:60: warning: 'nlb' may be used uninitialized in this function [-Wmaybe-uninitialized]
  220 |             if (ls != nxt4[i][j] && rs + dist4[i][j] < nrs && lst4[i][j] != nlb && nxt4[i][j] != -1 && lst4[i][j] != -1) { nrs = rs + dist4[i][j]; nls = lst4[i][j]; }
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 456 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 456 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 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 456 KB Output is correct
13 Correct 0 ms 456 KB Output is correct
14 Incorrect 1 ms 348 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 456 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 456 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 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 456 KB Output is correct
13 Correct 0 ms 456 KB Output is correct
14 Incorrect 1 ms 348 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 456 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 456 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 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 456 KB Output is correct
13 Correct 0 ms 456 KB Output is correct
14 Incorrect 1 ms 348 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 456 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 456 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 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 456 KB Output is correct
13 Correct 0 ms 456 KB Output is correct
14 Incorrect 1 ms 348 KB Output isn't correct
15 Halted 0 ms 0 KB -