Submission #1160499

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160499		Zero_OP	Wild Boar (JOI18_wild_boar)	C++20	47 / 100	18090 ms	146204 KiB

wild_boar

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, l, r) for(int i = (l); i < (r); ++i)
#define ROF(i, r, l) for(int i = (r) - 1; i >= (l); --i)

#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second

#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define sz(v) (int)v.size()
#define compact(v) v.erase(unique(all(v)), end(v))
#define pb push_back
#define eb emplace_back

#define readFile(task) freopen(task, "r", stdin)
#define writeFile(task) freopen(task, "w", stdout)
#define dbg(x) "[" #x " = " << (x) << "]"

template<typename T>
      bool minimize(T& a, const T& b){
            if(a > b) return a = b, true;
            return false;
      }

template<typename T>
      bool maximize(T& a, const T& b){
            if(a < b) return a = b, true;
            return false;
      }

using ll = long long;
using db = double;
using str = string;

using ull = unsigned long long;
using ldb = long double;

using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<db, db>;

using vi = vector<int>;
using vl = vector<ll>;
using vb = vector<bool>;
using vc = vector<char>;
using vs = vector<str>;

using vpi = vector<pi>;
using vpl = vector<pl>;
using vpd = vector<pd>;

using vvi = vector<vi>;
using vvl = vector<vl>;

void setIO(){
      ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef LOCAL
      readFile("task.inp");
      writeFile("task.out");
#endif // LOCAL
}

template<typename T, typename U>
ostream& operator << (ostream& out, pair<T, U> p){
      return out << '(' << p.ff << ',' << p.ss << ')';
}

void testcase(){
      int N, M, T, L;
      cin >> N >> M >> T >> L;

      vector<vector<tuple<int, int, int>>> adj(N);
      vvi idx(N, vi(M, -1));
      int nn = 0;
      vpi e(2 * M);

      FOR(i, 0, M){
            int u, v, w;
            cin >> u >> v >> w;
            --u, --v;
            adj[u].eb(v, i, w);
            adj[v].eb(u, i, w);
            e[idx[u][i] = nn++] = mp(u, i);
            e[idx[v][i] = nn++] = mp(v, i);
      }

      const ll inf = 1e18;
      using node = tuple<ll, int, int>;
      priority_queue<node, vector<node>, greater<node>> pq;

      auto dijkstra1 = [&](int p){
            vl d(nn, inf);
            d[p] = 0;
//            cout << dbg(e[p]) << '\n';
            pq.push(mt(0, e[p].ff, e[p].ss));
            while(!pq.empty()){
                  ll dist; int u, pre; tie(dist, u, pre) = pq.top(); pq.pop();
                  if(d[idx[u][pre]] != dist) continue;

//                  cout << dbg(u) << dbg(pre) << dbg(dist) << '\n';

                  for(auto &[v, id, w] : adj[u]) if(id != pre){
                        if(d[idx[v][id]] > dist + w){
                              d[idx[v][id]] = dist + w;
                              pq.push(mt(d[idx[v][id]], v, id));
                        }
                  }
            }
//            cout << '\n';
            return d;
      };

      auto dijkstra2 = [&](int s){
            vl d(nn, inf);
            for(auto [t, id, w] : adj[s]){
                  d[idx[t][id]] = w;
                  pq.push(mt(w, t, id));
            }

//            cout << dbg(s) << '\n';
            while(!pq.empty()){
                  ll dist; int u, pre; tie(dist, u, pre) = pq.top(); pq.pop();
                  if(d[idx[u][pre]] != dist) continue;
//                  cout << dbg(u) << dbg(pre) << dbg(dist) << '\n';
                  for(auto &[v, id, w] : adj[u]) if(id != pre){
                        if(d[idx[v][id]] > dist + w){
                              d[idx[v][id]] = dist + w;
                              pq.push(mt(d[idx[v][id]], v, id));
                        }
                  }
            }
//            cout << '\n';
            return d;
      };

      vvl dists(nn);
      FOR(i, 0, nn){
            dists[i] = dijkstra1(i);
      }

      vvl free_start_dists(N);
      FOR(i, 0, N){
            free_start_dists[i] = dijkstra2(i);
      }


      vi X(L);
      FOR(i, 0, L) cin >> X[i], --X[i];

      auto solve = [&](){
            vl dp(nn, inf);
//            FOR(i, 0, L) cout << X[i] << ' '; cout << '\n';
            for(auto &[v, id, w] : adj[X[1]]){
                  minimize(dp[idx[X[1]][id]], free_start_dists[X[0]][idx[X[1]][id]]);
//                  cout << dbg(X[1]) << dbg(id) << dbg(dp[idx[X[1]][id]]) << '\n';
            }

            FOR(i, 2, L){
                  vl nw(nn, inf);
                  for(auto &[v, idv, _] : adj[X[i]]){
                        int t = idx[X[i]][idv];
                        for(auto &[u, idu, __] : adj[X[i-1]]){
                              int s = idx[X[i-1]][idu];
                              minimize(nw[t], dp[s] + dists[s][t]);
//                              cout << dbg(nw[t]) << dbg(t) << dbg(e[s]) << dbg(e[t]) << dbg(dp[s] + dists[s][t]) << '\n';
                        }
                  }
                  swap(nw, dp);
            }

            ll res = *min_element(all(dp));
            if(res == inf) res = -1;
            return res;
      };

      while(T--){
            int P, Q;
            cin >> P >> Q;
            --P, --Q;
            X[P] = Q;
            cout << solve() << '\n';
      }
}

int main(){
      setIO();

      int T = 1;
//      cin >> T;
      while(T--) testcase();
      return 0;
}

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