oj.uz

Submission #388054

# Submission time Handle Problem Language Result Execution time Memory
388054 2021-04-09T19:58:28 Z Hegdahl Robot (JOI21_ho_t4) C++17
34 / 100
 3000 ms 277868 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);
  }
};

const int mxN = 1e5;

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

vector<ll> dist[mxN];

gp_hash_table<ll, ll, hsh> ccnt[mxN], csum[mxN];

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});
    ++ccnt[i][c];
    ++ccnt[j][c];
    csum[i][c] += p;
    csum[j][c] += p;
  }

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

  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;

    DEBUG(ar<ll, 2>{i, j});
    DEBUG(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 = csum[i][color] - w;
      ll cnt = ccnt[i][color];
      if (color == changed) {
        others -= g[i][j][2];
        --cnt;
      }

      if (cnt == 1 && dist[nxt][g[nxt].size()] == -1)
        pq.push({cost, nxt, g[nxt].size()});
      else {
        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:107: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]
  107 |     if (j < g[i].size()) changed = g[i][j][1];
      |         ~~^~~~~~~~~~~~~
Main.cpp:121:40: 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]
  121 |         pq.push({cost, nxt, g[nxt].size()});
      |                             ~~~~~~~~~~~^~
Main.cpp:123: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]
  123 |         pq.push({cost+others, nxt, g[nxt].size()});
      |                                    ~~~~~~~~~~~^~

Subtask #1
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 65972 KB Output is correct
2 Correct 54 ms 66012 KB Output is correct
3 Correct 55 ms 66116 KB Output is correct
4 Correct 54 ms 65952 KB Output is correct
5 Correct 54 ms 65988 KB Output is correct
6 Correct 54 ms 66088 KB Output is correct
7 Correct 66 ms 67812 KB Output is correct
8 Correct 59 ms 66964 KB Output is correct
9 Correct 1264 ms 115708 KB Output is correct
10 Correct 682 ms 91172 KB Output is correct
11 Correct 1187 ms 164892 KB Output is correct
12 Correct 408 ms 90976 KB Output is correct
13 Correct 1156 ms 164876 KB Output is correct
14 Correct 1193 ms 164772 KB Output is correct
15 Correct 71 ms 66164 KB Output is correct
16 Correct 60 ms 66448 KB Output is correct
17 Correct 60 ms 66500 KB Output is correct
18 Correct 55 ms 66076 KB Output is correct
19 Correct 125 ms 72600 KB Output is correct
20 Correct 56 ms 66164 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1126 ms 124160 KB Output is correct
2 Correct 390 ms 82332 KB Output is correct
3 Execution timed out 3078 ms 277868 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 65972 KB Output is correct
2 Correct 54 ms 66012 KB Output is correct
3 Correct 55 ms 66116 KB Output is correct
4 Correct 54 ms 65952 KB Output is correct
5 Correct 54 ms 65988 KB Output is correct
6 Correct 54 ms 66088 KB Output is correct
7 Correct 66 ms 67812 KB Output is correct
8 Correct 59 ms 66964 KB Output is correct
9 Correct 1264 ms 115708 KB Output is correct
10 Correct 682 ms 91172 KB Output is correct
11 Correct 1187 ms 164892 KB Output is correct
12 Correct 408 ms 90976 KB Output is correct
13 Correct 1156 ms 164876 KB Output is correct
14 Correct 1193 ms 164772 KB Output is correct
15 Correct 71 ms 66164 KB Output is correct
16 Correct 60 ms 66448 KB Output is correct
17 Correct 60 ms 66500 KB Output is correct
18 Correct 55 ms 66076 KB Output is correct
19 Correct 125 ms 72600 KB Output is correct
20 Correct 56 ms 66164 KB Output is correct
21 Correct 1126 ms 124160 KB Output is correct
22 Correct 390 ms 82332 KB Output is correct
23 Execution timed out 3078 ms 277868 KB Time limit exceeded
24 Halted 0 ms 0 KB -