oj.uz

Submission #388053

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

map<ll, ll> ccnt[mxN];
map<ll, ll> 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:95: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]
   95 |   pq.push({0, 0, g[0].size()});
      |                  ~~~~~~~~~^~
Main.cpp:108: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]
  108 |     if (j < g[i].size()) changed = g[i][j][1];
      |         ~~^~~~~~~~~~~~~
Main.cpp:122: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]
  122 |         pq.push({cost, nxt, g[nxt].size()});
      |                             ~~~~~~~~~~~^~
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 9 ms 14284 KB Output is correct
2 Correct 9 ms 14404 KB Output is correct
3 Correct 11 ms 14412 KB Output is correct
4 Correct 9 ms 14332 KB Output is correct
5 Correct 9 ms 14372 KB Output is correct
6 Correct 9 ms 14408 KB Output is correct
7 Correct 22 ms 16148 KB Output is correct
8 Correct 17 ms 15308 KB Output is correct
9 Correct 1382 ms 64224 KB Output is correct
10 Correct 714 ms 39548 KB Output is correct
11 Correct 1168 ms 113376 KB Output is correct
12 Correct 351 ms 39424 KB Output is correct
13 Correct 1118 ms 113372 KB Output is correct
14 Correct 1125 ms 113280 KB Output is correct
15 Correct 10 ms 14556 KB Output is correct
16 Correct 18 ms 14980 KB Output is correct
17 Correct 13 ms 15116 KB Output is correct
18 Correct 9 ms 14552 KB Output is correct
19 Correct 81 ms 21036 KB Output is correct
20 Correct 11 ms 14748 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1172 ms 80960 KB Output is correct
2 Correct 335 ms 35204 KB Output is correct
3 Execution timed out 3084 ms 230792 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14284 KB Output is correct
2 Correct 9 ms 14404 KB Output is correct
3 Correct 11 ms 14412 KB Output is correct
4 Correct 9 ms 14332 KB Output is correct
5 Correct 9 ms 14372 KB Output is correct
6 Correct 9 ms 14408 KB Output is correct
7 Correct 22 ms 16148 KB Output is correct
8 Correct 17 ms 15308 KB Output is correct
9 Correct 1382 ms 64224 KB Output is correct
10 Correct 714 ms 39548 KB Output is correct
11 Correct 1168 ms 113376 KB Output is correct
12 Correct 351 ms 39424 KB Output is correct
13 Correct 1118 ms 113372 KB Output is correct
14 Correct 1125 ms 113280 KB Output is correct
15 Correct 10 ms 14556 KB Output is correct
16 Correct 18 ms 14980 KB Output is correct
17 Correct 13 ms 15116 KB Output is correct
18 Correct 9 ms 14552 KB Output is correct
19 Correct 81 ms 21036 KB Output is correct
20 Correct 11 ms 14748 KB Output is correct
21 Correct 1172 ms 80960 KB Output is correct
22 Correct 335 ms 35204 KB Output is correct
23 Execution timed out 3084 ms 230792 KB Time limit exceeded
24 Halted 0 ms 0 KB -