Submission #1161626

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161626		Zero_OP	Wild Boar (JOI18_wild_boar)	C++20	62 / 100	18098 ms	375040 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, 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();
      }

      bool insert(const path& p){
            if(sz(paths) >= KEEP) return false;
            bool equal_s = false, equal_t = false;
            FOR(i, 0, sz(paths)){
                  if(paths[i].s == p.s && paths[i].t == p.t) return false;
                  if(paths[i].s == p.s){
                        if(equal_s) return false;
                        equal_s = true;
                  }

                  if(paths[i].t == p.t){
                        if(equal_t) return false;
                        equal_t = true;
                  }
            }
            paths.pb(p);
            return true;
      }

      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();
      vector<path> cur;
      FOR(i, 0, sz(a.paths)){
            FOR(j, 0, sz(b.paths)){
                  if(a.paths[i].t != b.paths[j].s){
                        cur.pb(path(a.paths[i].s, b.paths[j].t, a.paths[i].dist + b.paths[j].dist));
                  }
            }
      }

      sort(all(cur));
      FOR(i, 0, sz(cur)){
            result.insert(cur[i]);
      }
}

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]);
      }
}

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);
            assert(idx[u][v] == -1 && idx[v][u] == -1);
            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 [v, w] : adj[s]){
                  pq.push(mt(w, v, s, v));
            }

            vi cnt(N);
            while(!pq.empty()){
                  ll dist; int a, b, u;
                  tie(dist, a, b, u) = pq.top(); pq.pop();
                  if(!options[s][u].insert(path(a, b, dist))) continue;
                  for(auto [v, w] : adj[u]) if(v != b){
                        pq.push(mt(dist + w, a, u, v));
                  }
            }
      }

      // cout <<  X[53] << ' ' << X[54] << '\n';
//      cout << st[1].get() << '\n';
//      return 0;
//            FOR(i, 0, L) cout << X[i] << ' '; cout << '\n';

      // cout << dbg(X[52]) << dbg(X[53]) << dbg(X[54]) << '\n';
      // options[1][2].debug();
      // cout << '\n' << '\n';

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

            assert(X[0] != X[1]);
            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);
                  assert(X[i] != X[i+1]);


                  // if(i == L-3){
                  //       cur.debug();
                  //       cout << '\n';
                  // }
            }

            // FOR(i, 0, L) cout << X[i] << ' '; cout << '\n';
            // cur.debug();
            cout << cur.get() << '\n';
      }

      return 0;
}

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