oj.uz

Submission #388060

# Submission time Handle Problem Language Result Execution time Memory
388060 2021-04-09T20:10:57 Z Hegdahl Robot (JOI21_ho_t4) C++17
34 / 100
 3000 ms 430376 KB 
#pragma GCC optimize("Ofast")
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#ifdef ENABLE_DEBUG
#include <debug.h>
#else
#define DEBUG(...) do {} while (0)
#endif

using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using ull = unsigned long long;
using lll = __int128;
using ulll = unsigned __int128;

using ld = long double;

template<typename T, size_t N> using ar = array<T, N>;

template<typename T, typename Cmp = less<T>>
using iset = tree<T, null_type, Cmp, rb_tree_tag,
		  tree_order_statistics_node_update, allocator<T>>;

#define REPSI(name, start, stop, step) for (ll name = start; name < (ll)stop; name += step)
#define REPS(name, start, stop) REPSI(name, start, stop, 1)
#define REP(name, stop) REPS(name, 0, stop)

#define RREPSI(name, start, stop, step) for (ll name = stop-1; name >= (ll)start; name -= step)
#define RREPS(name, start, stop) RREPSI(name, start, stop, 1)
#define RREP(name, stop) RREPS(name, 0, stop)

template<typename T> void cins(T &first) { cin >> first; }
template<typename T, typename... Ts> void cins(T &first, T &second, Ts&... rest) {
  cin >> first;
  cins(second, rest...);
}

#define GET(type, ...) type __VA_ARGS__; cins(__VA_ARGS__)
#define GETI(...) GET(int, __VA_ARGS__)
#define GETLL(...) GET(ll, __VA_ARGS__)
#define GETS(...) GET(string, __VA_ARGS__)
#define GETD(...) GET(double, __VA_ARGS__)
#define GETC(...) GET(char, __VA_ARGS__)

struct hsh {
  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
    x += FIXED_RANDOM;
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
  size_t operator()(ar<int, 2> a) const {
    return hsh{}((ll(a[0])<<32) | a[1]);
  }
};

const int mxN = 1e5;

vector<ar<ll, 4>> g[mxN];

vector<ll> dist[mxN];

gp_hash_table<ar<int, 2>, ll, hsh> cc;

int main() {
  ios::sync_with_stdio(0);cin.tie(0);

  GETI(n, m);
  REP(mm, m) {
    GETI(i, j, c, p); --i, --j;

    ll oi = g[i].size();
    ll oj = g[j].size();

    g[i].push_back({j, c, p, oj});
    g[j].push_back({i, c, p, oi});

    cc[{i, c}] += p;
    cc[{j, c}] += p;
  }

  REP(i, n) dist[i].resize(g[i].size()+1, -1);

  // cost, i, j
  priority_queue<ar<ll, 3>, vector<ar<ll, 3>>, greater<ar<ll, 3>>> pq;
  
  pq.push({0, 0, g[0].size()});

  while (pq.size()) {
    auto [cost, i, j] = pq.top();
    pq.pop();
    
    if (dist[i][j] != -1) continue;
    dist[i][j] = cost;

    if (dist[i].back()==-1) dist[i].back() = cost;

    ll changed = -1;
    if (j < g[i].size()) changed = g[i][j][1];

    REP(k, g[i].size()) {
      if (k == j) continue;
      auto [nxt, color, w, nj] = g[i][k];
      
      ll others = cc.find({i, color})->second-w;

      if (color == changed)
        others -= g[i][j][2];

      ll no_edit = dist[nxt][g[nxt].size()];
      ll edit = dist[nxt][nj];

      if (edit == -1)
        pq.push({cost+w, nxt, nj});

      if (no_edit == -1)
        pq.push({cost+others, nxt, g[nxt].size()});

    }
  }

  REP(i, n) DEBUG(dist[i]);

  ll ans = 1LL<<60;
  for (ll x : dist[n-1]) if (x != -1) ans = min(ans, x);

  if (ans == (1LL<<60)) ans = -1;
  cout << ans << '\n';
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:94:27: warning: narrowing conversion of 'g[0].std::vector<std::array<long long int, 4> >::size()' from 'std::vector<std::array<long long int, 4> >::size_type' {aka 'long unsigned int'} to 'long long int' [-Wnarrowing]
   94 |   pq.push({0, 0, g[0].size()});
      |                  ~~~~~~~~~^~
Main.cpp:106:11: warning: comparison of integer expressions of different signedness: 'std::tuple_element<2, std::array<long long int, 3> >::type' {aka 'long long int'} and 'std::vector<std::array<long long int, 4> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |     if (j < g[i].size()) changed = g[i][j][1];
      |         ~~^~~~~~~~~~~~~
Main.cpp:112:28: warning: narrowing conversion of 'i' from 'std::tuple_element<1, std::array<long long int, 3> >::type' {aka 'long long int'} to 'int' [-Wnarrowing]
  112 |       ll others = cc.find({i, color})->second-w;
      |                            ^
Main.cpp:112:31: warning: narrowing conversion of 'color' from 'std::tuple_element<1, std::array<long long int, 4> >::type' {aka 'long long int'} to 'int' [-Wnarrowing]
  112 |       ll others = cc.find({i, color})->second-w;
      |                               ^~~~~
Main.cpp:124:47: warning: narrowing conversion of 'g[nxt].std::vector<std::array<long long int, 4> >::size()' from 'std::vector<std::array<long long int, 4> >::size_type' {aka 'long unsigned int'} to 'long long int' [-Wnarrowing]
  124 |         pq.push({cost+others, nxt, g[nxt].size()});
      |                                    ~~~~~~~~~~~^~

Subtask #1
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 4 ms 4940 KB Output is correct
6 Correct 4 ms 4940 KB Output is correct
7 Correct 9 ms 5648 KB Output is correct
8 Correct 5 ms 5324 KB Output is correct
9 Correct 534 ms 30196 KB Output is correct
10 Correct 290 ms 30032 KB Output is correct
11 Correct 114 ms 17656 KB Output is correct
12 Correct 139 ms 17720 KB Output is correct
13 Correct 110 ms 11456 KB Output is correct
14 Correct 126 ms 17608 KB Output is correct
15 Correct 5 ms 5196 KB Output is correct
16 Correct 7 ms 5324 KB Output is correct
17 Correct 6 ms 5452 KB Output is correct
18 Correct 4 ms 5068 KB Output is correct
19 Correct 42 ms 8516 KB Output is correct
20 Correct 5 ms 5260 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 468 ms 32288 KB Output is correct
2 Correct 136 ms 18268 KB Output is correct
3 Correct 1672 ms 72200 KB Output is correct
4 Correct 233 ms 20180 KB Output is correct
5 Execution timed out 3076 ms 430376 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 4 ms 4940 KB Output is correct
6 Correct 4 ms 4940 KB Output is correct
7 Correct 9 ms 5648 KB Output is correct
8 Correct 5 ms 5324 KB Output is correct
9 Correct 534 ms 30196 KB Output is correct
10 Correct 290 ms 30032 KB Output is correct
11 Correct 114 ms 17656 KB Output is correct
12 Correct 139 ms 17720 KB Output is correct
13 Correct 110 ms 11456 KB Output is correct
14 Correct 126 ms 17608 KB Output is correct
15 Correct 5 ms 5196 KB Output is correct
16 Correct 7 ms 5324 KB Output is correct
17 Correct 6 ms 5452 KB Output is correct
18 Correct 4 ms 5068 KB Output is correct
19 Correct 42 ms 8516 KB Output is correct
20 Correct 5 ms 5260 KB Output is correct
21 Correct 468 ms 32288 KB Output is correct
22 Correct 136 ms 18268 KB Output is correct
23 Correct 1672 ms 72200 KB Output is correct
24 Correct 233 ms 20180 KB Output is correct
25 Execution timed out 3076 ms 430376 KB Time limit exceeded
26 Halted 0 ms 0 KB -