Submission #752316

#	Time	Username	Problem	Language	Result	Execution time	Memory
752316		tch1cherin	Olympic Bus (JOI20_ho_t4)	C++17	37 / 100	1074 ms	220216 KiB

ho_t4

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt,fma")
#include <bits/stdc++.h>
using namespace std;

// Trash code from https://www.geeksforgeeks.org/pairing-heap/
struct HeapNode {
    pair<int, int> key;
    HeapNode *leftChild;
    HeapNode *nextSibling;
 
    HeapNode():
        leftChild(NULL), nextSibling(NULL) {}
 
    // creates a new node
    HeapNode(pair<int, int> key_, HeapNode *leftChild_, HeapNode *nextSibling_):
        key(key_), leftChild(leftChild_), nextSibling(nextSibling_) {}
         
        // Adds a child and sibling to the node
    void addChild(HeapNode *node) {
        if(leftChild == NULL)
            leftChild = node;
        else {
            node->nextSibling = leftChild;
            leftChild = node;
        }
    }
};
 
// Returns true if root of the tree
// is null otherwise returns false
bool Empty(HeapNode *node) {
    return (node == NULL);
}
 
// Function to merge two heaps
HeapNode *Merge(HeapNode *A, HeapNode *B)
{
    // If any of the two-nodes is null
    // the return the not null node
    if(A == NULL) return B;
    if(B == NULL) return A;
     
    // To maintain the min heap condition compare   
    // the nodes and node with minimum value become 
    // parent of the other node
    if(A->key.first < B->key.first) {                 
        A->addChild(B);
        return A;        
    }
    else {
        B->addChild(A);
        return B;
    }
 
    return NULL; // Unreachable
}
 
// Returns the root value of the heap
pair<int, int> Top(HeapNode *node) {
    return node->key;
}
 
// Function to insert the new node in the heap
HeapNode *Insert(HeapNode *node, pair<int, int> key) {
    return Merge(node, new HeapNode(key, NULL, NULL));
}
 
// This method is used when we want to delete root node
HeapNode *TwoPassMerge(HeapNode *node) {
    if(node == NULL || node->nextSibling == NULL)
        return node;
    else {
        HeapNode *A, *B, *newNode;
        A = node;
        B = node->nextSibling;
        newNode = node->nextSibling->nextSibling;
 
        A->nextSibling = NULL;
        B->nextSibling = NULL;
 
        return Merge(Merge(A, B), TwoPassMerge(newNode));
    }
 
    return NULL; // Unreachable
}
 
// Function to delete the root node in heap
HeapNode *Delete(HeapNode *node) {
    return TwoPassMerge(node->leftChild);
}
 
struct PairingHeap {
    HeapNode *root;
 
    PairingHeap():
        root(NULL) {}
 
    bool Empty(void) {
        return ::Empty(root);
    }
 
    pair<int, int> Top(void) {
        return ::Top(root);
    }
 
    void Insert(pair<int, int> key) {
        root = ::Insert(root, key);
    }
 
    void Delete(void) {
        root = ::Delete(root);
    }
 
    void Join(PairingHeap other) {
        root = ::Merge(root, other.root);
    }
     
};

const int N = 200, M = 50000;
vector<int> graph[2][N];
int deg[N], rev_deg[N], path[N], dist[N], _from[M], _to[M], weight[M], cost[M];
int dist_w[4][M][N], dist_i[4][N];
int n, m;

int from(int g, int id) {
  return g == 0 ? _from[id] : _to[id];
}

int to(int g, int id) {
  return g == 0 ? _to[id] : _from[id];
}

void dijkstra(int start, int g, bool flag, int del = -1) {
  fill(dist, dist + n, INT_MAX);
  if (flag) fill(path, path + n, -1);
  dist[start] = 0;
  PairingHeap q;
  q.Insert({0, start});
  while (!q.Empty()) {
    auto [d, u] = q.Top();
    q.Delete();
    if (dist[u] > d) {
      continue;
    }
    for (int e : graph[g][u]) {
      if (e != del && dist[u] + weight[e] < dist[to(g, e)]) {
        dist[to(g, e)] = dist[u] + weight[e];
        if (flag) path[to(g, e)] = e;
        q.Insert({dist[to(g, e)], to(g, e)});
      }
    }
  }
}

void _solve(int g, int start, int it) {
  dijkstra(start, g, true);
  memcpy(dist_i[it], dist, sizeof dist);
  for (int i = 0; i < n; i++) {
    if (path[i] != -1) {
      dijkstra(start, g, false, path[i]);
      memcpy(dist_w[it][path[i]], dist, sizeof dist);
    }
  }
}

int Get(int it, int id, int u) {
  return dist_w[it][id][u] == -1 ? dist_i[it][u] : dist_w[it][id][u];
}

void solve() {
  cin >> n >> m;
  memset(dist_w, -1, sizeof dist_w);
  for (int i = 0; i < m; i++) {
    cin >> _from[i] >> _to[i] >> weight[i] >> cost[i];
    _from[i]--, _to[i]--;
    deg[_from[i]]++, rev_deg[_to[i]]++;
  }
  for (int i = 0; i < n; i++) {
    graph[0][i].reserve(deg[i]);
    graph[1][i].reserve(rev_deg[i]);
  }
  for (int i = 0; i < m; i++) {
    graph[0][_from[i]].push_back(i);
    graph[1][_to[i]].push_back(i);
  }
  _solve(0, 0, 0);
  _solve(0, n - 1, 1);
  _solve(1, 0, 2);
  _solve(1, n - 1, 3);
  int ans = INT_MAX;
  if (dist_i[0][n - 1] != INT_MAX && dist_i[1][0] != INT_MAX) {
    ans = dist_i[0][n - 1] + dist_i[1][0];
  }
  for (int u = 0; u < n; u++) {
    for (int id : graph[0][u]) {
      int AB = INT_MAX, BA = INT_MAX;
      AB = min(AB, Get(0, id, n - 1));
      if (Get(0, id, to(0, id)) != INT_MAX && Get(3, id, from(0, id)) != INT_MAX) {
        AB = min(AB, Get(0, id, to(0, id)) + Get(3, id, from(0, id)) + weight[id]);
      }
      BA = min(BA, Get(1, id, 0));
      if (Get(1, id, to(0, id)) != INT_MAX && Get(2, id, from(0, id)) != INT_MAX) {
        BA = min(BA, Get(1, id, to(0, id)) + Get(2, id, from(0, id)) + weight[id]); 
      }
      if (AB == INT_MAX || BA == INT_MAX) {
        continue;
      }
      ans = min(ans, AB + BA + cost[id]);
    }
  }
  cout << (ans == INT_MAX ? -1 : ans) << "\n";
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  solve();
}

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 21 / 21
• Subtask 4: 0 / 63