Submission #1145131

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145131		mgl_diamond	Robot (JOI21_ho_t4)	C++17	34 / 100	3095 ms	58676 KiB

Main

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
 
#define foru(i, l, r) for(int i=(l); i<=(r); ++i)
#define ford(i, l, r) for(int i=(l); i>=(r); --i)
#define fore(x, v) for(auto &x : v)
#define all(x) (x).begin(), (x).end()
#define siz(x) (int)(x).size()
#define pow2(x) (1ll << (x))
#define on(mask, x) ((mask >> x & 1) == 1)
#define off(mask, x) ((mask >> x & 1) == 0)
#define mp make_pair
#define vec vector
#define ar array
#define fi first
#define se second
#define pii pair<int, int>
#define out(x) cout << #x << " " << x << "\n"
template<class T> bool ckmin(T &a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T> bool ckmax(T &a, T b) { if (a < b) { a = b; return 1; } return 0; }
 
void setIO() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  #define task "input"
  if (fopen(task".inp", "r")) {
    freopen(task".inp", "r", stdin);
    freopen(task".out", "w", stdout);
  }
}

const ll LINF = 1e18+18;
const int INF = 1e9+9;
const int N = 2e5+5;
int n, m;

struct Edge {
  int a[2];
  int c, p;
  Edge (int _u=0, int _v=0, int _c=0, int _p=0) {
    a[0] = _u;
    a[1] = _v;
    c = _c;
    p = _p;
  }
  int other(int u) {
    return a[0]^a[1]^u;
  }
};

vector<Edge> edges;
vector<int> adj[N];
map<int, ll> color[N];
ll dp[N][2][2];

int main() {
  setIO();

  cin >> n >> m;

  for (int i = 0; i < m; ++i) {
    int u, v, c, p;
    cin >> u >> v >> c >> p;
    if (u > v) swap(u, v);
    adj[u].push_back(siz(edges));
    adj[v].push_back(siz(edges));
    edges.emplace_back(u, v, c, p);
    color[u][c] += p;
    color[v][c] += p;
  }

  priority_queue<pair<ll, pair<int, pii>>> pq;
  memset(dp, 0x3f, sizeof(dp));

  // edge - side - used-or-not
  for (int i : adj[1]) {
    int v = edges[i].a[1];
    dp[i][1][0] = color[1][edges[i].c] - edges[i].p;
    pq.push({-dp[i][1][0], {i, {1, 0}}});
    dp[i][1][1] = edges[i].p;
    pq.push({-dp[i][1][1], {i, {1, 1}}});
  }

  while (!pq.empty()) {
    auto top = pq.top();
    pq.pop();

    ll w = -top.fi;
    int i = top.se.fi;
    bool side = top.se.se.fi, change = top.se.se.se;
    if (w != dp[i][side][change]) continue;

    int u = edges[i].a[side];
    if (u == n) {
      cout << w;
      return 0;
    }

    for (int j : adj[u]) if (i != j) {
      bool nside = (edges[j].other(u) > u);
      if (change) {
        if (ckmin(dp[j][nside][0], w + color[u][edges[j].c] - edges[j].p - (edges[i].c == edges[j].c ? edges[i].p : 0))) {
          pq.push({-dp[j][nside][0], {j, {nside, 0}}});
        }
        if (ckmin(dp[j][nside][1], w + edges[j].p)) {
          pq.push({-dp[j][nside][1], {j, {nside, 1}}});
        }
      }
      else {
        if (ckmin(dp[j][nside][0], w + color[u][edges[j].c] - edges[j].p)) {
          pq.push({-dp[j][nside][0], {j, {nside, 0}}});
        }
        if (ckmin(dp[j][nside][1], w + edges[j].p)) {
          pq.push({-dp[j][nside][1], {j, {nside, 1}}});
        }
      }
    }
  }

  cout << -1;
}

Compilation message (stderr)

Main.cpp: In function 'void setIO()':
Main.cpp:31:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |     freopen(task".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:32:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |     freopen(task".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 34 / 34
• Subtask 2: 0 / 24
• Subtask 3: 0 / 42