oj.uz

Submission #388058

# Submission time Handle Problem Language Result Execution time Memory
388058 2021-04-09T20:04:11 Z Hegdahl Robot (JOI21_ho_t4) C++17
34 / 100
 3000 ms 219824 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;

    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[{i, color}]-w;

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

      pq.push({cost+others, nxt, g[nxt].size()});

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

  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:104: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]
  104 |     if (j < g[i].size()) changed = g[i][j][1];
      |         ~~^~~~~~~~~~~~~
Main.cpp:110:23: warning: narrowing conversion of 'i' from 'std::tuple_element<1, std::array<long long int, 3> >::type' {aka 'long long int'} to 'int' [-Wnarrowing]
  110 |       ll others = cc[{i, color}]-w;
      |                       ^
Main.cpp:110:26: warning: narrowing conversion of 'color' from 'std::tuple_element<1, std::array<long long int, 4> >::type' {aka 'long long int'} to 'int' [-Wnarrowing]
  110 |       ll others = cc[{i, color}]-w;
      |                          ^~~~~
Main.cpp:115:45: 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]
  115 |       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 5068 KB Output is correct
7 Correct 16 ms 6728 KB Output is correct
8 Correct 10 ms 5964 KB Output is correct
9 Correct 1247 ms 54784 KB Output is correct
10 Correct 705 ms 30076 KB Output is correct
11 Correct 1291 ms 103880 KB Output is correct
12 Correct 384 ms 29936 KB Output is correct
13 Correct 1155 ms 103864 KB Output is correct
14 Correct 1178 ms 103788 KB Output is correct
15 Correct 5 ms 5196 KB Output is correct
16 Correct 9 ms 5324 KB Output is correct
17 Correct 10 ms 5560 KB Output is correct
18 Correct 4 ms 5068 KB Output is correct
19 Correct 73 ms 11528 KB Output is correct
20 Correct 6 ms 5196 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1116 ms 69188 KB Output is correct
2 Correct 336 ms 24428 KB Output is correct
3 Execution timed out 3104 ms 219824 KB Time limit exceeded
4 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 5068 KB Output is correct
7 Correct 16 ms 6728 KB Output is correct
8 Correct 10 ms 5964 KB Output is correct
9 Correct 1247 ms 54784 KB Output is correct
10 Correct 705 ms 30076 KB Output is correct
11 Correct 1291 ms 103880 KB Output is correct
12 Correct 384 ms 29936 KB Output is correct
13 Correct 1155 ms 103864 KB Output is correct
14 Correct 1178 ms 103788 KB Output is correct
15 Correct 5 ms 5196 KB Output is correct
16 Correct 9 ms 5324 KB Output is correct
17 Correct 10 ms 5560 KB Output is correct
18 Correct 4 ms 5068 KB Output is correct
19 Correct 73 ms 11528 KB Output is correct
20 Correct 6 ms 5196 KB Output is correct
21 Correct 1116 ms 69188 KB Output is correct
22 Correct 336 ms 24428 KB Output is correct
23 Execution timed out 3104 ms 219824 KB Time limit exceeded
24 Halted 0 ms 0 KB -