Submission #770103

#	Time	Username	Problem	Language	Result	Execution time	Memory
770103		mgl_diamond	Robot (JOI21_ho_t4)	C++14	34 / 100	3044 ms	49708 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
 
#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 sz(x) (int)(x).size()
#define fi first
#define se second
 
void setIO(string name) {
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  if (!name.empty()) {
    freopen((name + ".in").c_str(), "r", stdin);
    freopen((name + ".out").c_str(), "w", stdout);
  }
}
 
struct edge {
  int u, v, c, p;
  edge (int _u=0, int _v=0, int _c=0, int _p=0) : u(_u), v(_v), c(_c), p(_p) {}
  int oth(int node) { return node ^ u ^ v; }
};
 
struct state {
  ll cost;
  int u, need, i;
  state(ll _c=0, int _u=0, int _need=0, int _i=0) : cost(_c), u(_u), i(_i), need(_need) {}
  friend bool operator < (const state &a, const state &b) {
    return a.cost > b.cost;
  }
};
 
const ll LINF = 1e15;
const int N = 1e5+5;
const int M = 2e5+5;
 
int n, m;
edge e[M];
vector<int> graph[N], color[N];
vector<ll> dp[N][2], sum[N];
 
int get(vector<int> &v, int i) {
  return lower_bound(all(v), i) - v.begin();
}
 
int main() {
  setIO("");
 
  cin >> n >> m;
 
  foru(i, 1, m) {
    int u, v, c, p;
    cin >> u >> v >> c >> p;
    e[i] = edge(u, v, c, p);
    graph[u].push_back(i);
    graph[v].push_back(i);
    color[u].push_back(c);
    color[v].push_back(c);
  }
 
  foru(i, 1, n) {
    dp[i][0].resize(sz(graph[i]), LINF);
    dp[i][1].resize(sz(graph[i]), LINF);
    sort(all(color[i]));
    color[i].resize(unique(all(color[i])) - color[i].begin());
    sum[i].resize(color[i].size(), 0);
  }
 
  foru(i, 1, m) {
    sum[e[i].u][get(color[e[i].u], e[i].c)] += e[i].p;
    sum[e[i].v][get(color[e[i].v], e[i].c)] += e[i].p;
  }
 
  priority_queue<state> pq;
  pq.push(state(0, 1, -1, -1));
 
  while (!pq.empty()) {
    state at = pq.top(); pq.pop();
    int u = at.u, lst = at.i, need = at.need;
    // if (lst != -1) cout << at.cost << " " << u << " " << e[graph[u][lst]].oth(u) << " " << need << "\n";
    if (u == n) break;
    if (lst != -1 && dp[u][need][lst] != at.cost) continue;
 
    foru(i, 0, sz(graph[u])-1) {
      if (i == lst) continue;
      int idx = graph[u][i];
      int v = e[idx].oth(u);
      int kth = get(graph[v], idx), kthcolor = get(color[u], e[idx].c);
      ll cost;
      
      if (sum[u][kthcolor] == e[idx].c) {
        if (dp[v][0][kth] > at.cost) {
          dp[v][0][kth] = at.cost;
          pq.push(state(at.cost, v, 0, kth));
        }
        continue;
      }
 
      cost = at.cost + e[idx].p;
      if (dp[v][1][kth] > cost) {
        dp[v][1][kth] = cost;
        pq.push(state(cost, v, 1, kth));
      }
 
      cost = at.cost + sum[u][kthcolor] - e[idx].p;
      if (lst != -1 && e[graph[u][lst]].c == e[idx].c && need) {
        cost -= e[graph[u][lst]].p;
      }
      if (dp[v][0][kth] > cost) {
        dp[v][0][kth] = cost;
        pq.push(state(cost, v, 0, kth));
      }
    }
  }
 
  ll ans = LINF;
  foru(i, 0, sz(graph[n])-1) ans = min(ans, min(dp[n][0][i], dp[n][1][i]));
  cout << (ans == LINF ? -1 : ans);
}

Compilation message (stderr)

Main.cpp: In constructor 'state::state(ll, int, int, int)':
Main.cpp:31:16: warning: 'state::i' will be initialized after [-Wreorder]
   31 |   int u, need, i;
      |                ^
Main.cpp:31:10: warning:   'int state::need' [-Wreorder]
   31 |   int u, need, i;
      |          ^~~~
Main.cpp:32:3: warning:   when initialized here [-Wreorder]
   32 |   state(ll _c=0, int _u=0, int _need=0, int _i=0) : cost(_c), u(_u), i(_i), need(_need) {}
      |   ^~~~~
Main.cpp: In function 'void setIO(std::string)':
Main.cpp:18:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     freopen((name + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:19:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     freopen((name + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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