Submission #1161593

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161593		Zero_OP	Wild Boar (JOI18_wild_boar)	C++20	12 / 100	52 ms	103824 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 pb push_back
#define eb emplace_back
#define sz(v) (int)v.size()
#define sum_of(v) accumulate(all(v), 0ll)

#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 ld = long double;
using ull = unsigned long long;

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

using vi = vector<int>;
using vb = vector<bool>;
using vc = vector<char>;
using vl = vector<ll>;
using vd = vector<db>;

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

void setIO(){
      ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef LOCAL
      freopen("task.inp", "r", stdin);
      freopen("task.out", "w", stdout);
#endif // LOCAL
}

const int MAX = 1e5 + 5;
const ll inf = 1e18;
using dijkstra_node = tuple<ll, int, int>;

struct path{
      int s, t; ll dist;
      path(int s, int t, ll dist) : s(s), t(t), dist(dist) {}

      bool operator < (const path& o) const {
            return dist < o.dist;
      }
};

const int KEEP = 5;
struct info{
      vector<path> paths;

      info() : paths() {}

      void clear(){
            paths.clear();
      }

      void insert(const path& p){
            paths.pb(p);
      }

      void filter(){
            sort(all(paths));

            vector<path> result;
            FOR(i, 0, sz(paths)){
                  if(sz(result) >= KEEP) break;

                  bool need = true, equal_s = false, equal_t = false;
                  FOR(j, 0, sz(result)){
                        if(result[j].s == paths[i].s && result[j].t == paths[i].t){
                              need = false;
                              break;
                        }

                        if(result[j].s == paths[i].s) {
                              if(equal_s){
                                    need = false;
                                    break;
                              }

                              equal_s = true;
                        }

                        if(result[j].t == paths[i].t){
                              if(equal_t){
                                    need = false;
                                    break;
                              }

                              equal_t = true;
                        }
                  }

                  if(need) result.pb(paths[i]);
            }

            swap(paths, result);
      }

      ll get(){
            if(paths.empty()) return -1;
            return paths[0].dist;
      }

//      void debug(){
//            FOR(i, 0, sz(paths)){
//                  cout << '(' << paths[i].s << ' ' << paths[i].t << ' ' << paths[i].dist << ")\n";
//            }
//      }
} options[2000][2000], st[MAX << 2];
int X[MAX];

void pull(info& result, const info& a, const info& b){
      result.clear();
      FOR(i, 0, sz(a.paths)){
            FOR(j, 0, sz(b.paths)){
                  if(a.paths[i].t != b.paths[j].s){
//                        if(a.paths[i].dist + b.paths[j].dist >= inf){
//                              cout << a.paths[i].dist << ' ' << b.paths[j].dist << '\n';
//                              exit(0);
//                        }
//                        assert(a.paths[i].dist + b.paths[j].dist < inf);
                        result.insert(path(a.paths[i].s, b.paths[j].t, a.paths[i].dist + b.paths[j].dist));
                  }
            }
      }

      result.filter();
}

void refine(int id, int l, int r, int u, int v){
      if(l == r){
            st[id] = options[X[l]][X[l+1]];
      } else{
            int mid = l + r >> 1;
            if(u <= mid) refine(id << 1, l, mid, u, v);
            if(mid < v)  refine(id << 1 | 1, mid + 1, r, u, v);
            pull(st[id], st[id << 1], st[id << 1 | 1]);
//            cout << dbg(X[l]) << dbg(X[r+1]) << '\n';
//            st[id].debug();
//            cout << '\n';
      }
}

int main(){
      setIO();

      int N, M, T, L;
      cin >> N >> M >> T >> L;

      int cnt = 0;
      vector<vi> idx(N, vi(N, -1));
      vector<vpi> adj(N);
      vpi e(M * 2);
      FOR(i, 0, M){
            int u, v, w;
            cin >> u >> v >> w;
            --u, --v;
            adj[u].eb(v, w);
            adj[v].eb(u, w);
            e[idx[u][v] = cnt++] = mp(u, v);
            e[idx[v][u] = cnt++] = mp(v, u);
      }

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

      priority_queue<dijkstra_node, vector<dijkstra_node>, greater<dijkstra_node>> pq;

      FOR(s, 0, N){
            for(auto [_, __] : adj[s]){
                  vl dists(cnt, inf);

                  dists[idx[s][_]] = __;
                  pq.push(mt(__, _, s));

                  while(!pq.empty()){
                        ll dist; int u, pre; tie(dist, u, pre) = pq.top(); pq.pop();
                        if(dists[idx[u][pre]] < dist) continue;

                        for(auto [v, w] : adj[u]) if(v != pre){
                              int pos = idx[u][v];
                              if(dists[pos] > dist + w){
                                    dists[pos] = dist + w;
                                    pq.push(mt(dists[pos], v, u));
                              }
                        }
                  }

                  FOR(i, 0, 2 * M) if(dists[i] != inf){
                        int pre, cur;
                        tie(pre, cur) = e[i];
                        options[s][cur].insert(path(_, pre, dists[i]));
                  }
            }
      }

      while(T--){
            int P, Q;
            cin >> P >> Q;
            --P, --Q;
            X[P] = Q;

            info cur = options[X[0]][X[1]];
            FOR(i, 1, L-1){
                  info nw;
                  pull(nw, cur, options[X[i]][X[i+1]]);
                  swap(nw, cur);
            }
            cout << cur.get() << '\n';
      }

      return 0;
}

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