oj.uz

Submission #388059

# Submission time Handle Problem Language Result Execution time Memory
388059 2021-04-09T20:06:31 Z Hegdahl Robot (JOI21_ho_t4) C++17
34 / 100
 3000 ms 219976 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.find({i, color})->second-w;

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

      if (dist[nxt][g[nxt].size()] == -1)
        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: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]
  110 |       ll others = cc.find({i, color})->second-w;
      |                            ^
Main.cpp:110: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]
  110 |       ll others = cc.find({i, color})->second-w;
      |                               ^~~~~
Main.cpp:116: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]
  116 |         pq.push({cost+others, nxt, g[nxt].size()});
      |                                    ~~~~~~~~~~~^~

Subtask #1
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 4 ms 4940 KB Output is correct
4 Correct 4 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 9 ms 5648 KB Output is correct
8 Correct 8 ms 5580 KB Output is correct
9 Correct 556 ms 30152 KB Output is correct
10 Correct 355 ms 30088 KB Output is correct
11 Correct 1126 ms 103800 KB Output is correct
12 Correct 217 ms 17580 KB Output is correct
13 Correct 1066 ms 103848 KB Output is correct
14 Correct 1138 ms 103860 KB Output is correct
15 Correct 5 ms 5196 KB Output is correct
16 Correct 8 ms 5440 KB Output is correct
17 Correct 8 ms 5580 KB Output is correct
18 Correct 4 ms 5068 KB Output is correct
19 Correct 51 ms 8488 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 605 ms 44536 KB Output is correct
2 Correct 165 ms 18164 KB Output is correct
3 Execution timed out 3089 ms 219976 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 4 ms 4940 KB Output is correct
4 Correct 4 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 9 ms 5648 KB Output is correct
8 Correct 8 ms 5580 KB Output is correct
9 Correct 556 ms 30152 KB Output is correct
10 Correct 355 ms 30088 KB Output is correct
11 Correct 1126 ms 103800 KB Output is correct
12 Correct 217 ms 17580 KB Output is correct
13 Correct 1066 ms 103848 KB Output is correct
14 Correct 1138 ms 103860 KB Output is correct
15 Correct 5 ms 5196 KB Output is correct
16 Correct 8 ms 5440 KB Output is correct
17 Correct 8 ms 5580 KB Output is correct
18 Correct 4 ms 5068 KB Output is correct
19 Correct 51 ms 8488 KB Output is correct
20 Correct 6 ms 5196 KB Output is correct
21 Correct 605 ms 44536 KB Output is correct
22 Correct 165 ms 18164 KB Output is correct
23 Execution timed out 3089 ms 219976 KB Time limit exceeded
24 Halted 0 ms 0 KB -