Submission #1103907

#TimeUsernameProblemLanguageResultExecution timeMemory
1103907Zero_OPRobot (JOI21_ho_t4)C++14
100 / 100
800 ms96392 KiB
#include <bits/stdc++.h> using namespace std; #define rep(i, l, r) for(int i = (l), _r = (r); i < _r; ++i) #define FOR(i, l, r) for(int i = (l), _r = (r); i <= _r; ++i) #define ROF(i, r, l) for(int i = (r), _l = (l); i >= _l; --i) #define all(v) begin(v), end(v) #define compact(v) v.erase(unique(all(v)), end(v)) #define sz(v) (int)v.size() #define dbg(x) "[" #x " = " << (x) << "]" template<typename T> bool minimize(T& a, const T& b){ if(a > b) return a = b, true; return false; } template<typename T> bool maximize(T& a, const T& b){ if(a < b) return a = b, true; return false; } using ll = long long; using ld = long double; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); template<typename T> T random_int(T l, T r){ return uniform_int_distribution<T>(l, r)(rng); } template<typename T> T random_real(T l, T r){ return uniform_real_distribution<T>(l, r)(rng); } const int MAX = 2e5 + 5; struct DisjointSet{ vector<int> lab; DisjointSet(int n) : lab(n, -1) {} int root(int u){ return lab[u] < 0 ? u : (lab[u] = root(lab[u])); } bool unite(int u, int v){ u = root(u); v = root(v); if(u == v) return false; if(lab[u] > lab[v]) swap(u, v); lab[u] += lab[v]; lab[v] = u; return true; } bool same_set(int u, int v){ return root(u) == root(v); } }; int n, m; map<int, vector<pair<int, int>>> adj[MAX]; map<int, ll> same_color_sum[MAX]; ll dp[MAX]; map<int, ll> dp_last[MAX]; void testcase(){ cin >> n >> m; DisjointSet dsu(n + 1); while(m--){ int u, v, c, p; cin >> u >> v >> c >> p; dsu.unite(u, v); adj[u][c].push_back({v, p}); adj[v][c].push_back({u, p}); same_color_sum[u][c] += p; same_color_sum[v][c] += p; // cout << u << " " << c << " " << p << '\n'; // cout << v << " " << c << " " << p << '\n'; } if(!dsu.same_set(1, n)){ cout << -1 << '\n'; return; } memset(dp, 0x3f, sizeof(dp)); priority_queue<tuple<ll, int, int>> pq; pq.push({-(dp[1] = 0), 1, 0}); while(!pq.empty()){ ll mincost; int u, c; tie(mincost, u, c) = pq.top(); pq.pop(); mincost *= -1; // cout << dbg(u) << dbg(c) << dbg(mincost) << '\n'; if(c == 0){ if(mincost != dp[u]) continue; //last edge color does not matter for(auto [c, vec] : adj[u]){ ll tot = same_color_sum[u][c]; for(auto [v, w] : vec){ ll change_neighbours = dp[u] + tot - w; if(minimize(dp[v], change_neighbours)){ // cout << dbg(v) << dbg(change_neighbours) << '\n'; pq.push({-dp[v], v, 0}); //we can consider this edge as color 0 because it never goes back same edge } ll change_current = dp[u] + w; if(minimize(dp[v], change_current)){ // cout << dbg(v) << dbg(change_current) << '\n'; pq.push({-dp[v], v, 0}); //as same as above } ll keep = dp[u]; if(dp_last[v].find(c) == dp_last[v].end() || dp_last[v][c] > keep){ dp_last[v][c] = keep; pq.push({-keep, v, c}); } } } } else{ ll correct = dp_last[u][c]; if(mincost != correct) continue; ll tot = same_color_sum[u][c]; for(auto [v, w] : adj[u][c]){ ll change_neighbours = mincost + tot - w; if(minimize(dp[v], change_neighbours)){ pq.push({-dp[v], v, 0}); //consider same cases } } } } ll ans = dp[n]; cout << ans << '\n'; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); #define filename "task" if(fopen(filename".inp", "r")){ freopen(filename".inp", "r", stdin); freopen(filename".out", "w", stdout); } int T = 1; //cin >> T; while(T--) testcase(); return 0; }

Compilation message (stderr)

Main.cpp: In function 'bool minimize(T&, const T&)':
Main.cpp:15:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   15 |     if(a > b) return a = b, true; return false;
      |     ^~
Main.cpp:15:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   15 |     if(a > b) return a = b, true; return false;
      |                                   ^~~~~~
Main.cpp: In function 'bool maximize(T&, const T&)':
Main.cpp:20:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   20 |     if(a < b) return a = b, true; return false;
      |     ^~
Main.cpp:20:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   20 |     if(a < b) return a = b, true; return false;
      |                                   ^~~~~~
Main.cpp: In function 'void testcase()':
Main.cpp:98:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   98 |             for(auto [c, vec] : adj[u]){
      |                      ^
Main.cpp:100:26: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  100 |                 for(auto [v, w] : vec){
      |                          ^
Main.cpp:127:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  127 |             for(auto [v, w] : adj[u][c]){
      |                      ^
Main.cpp: In function 'int main()':
Main.cpp:147:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  147 |         freopen(filename".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:148:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  148 |         freopen(filename".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...