Submission #992612

#	Time	Username	Problem	Language	Result	Execution time	Memory
992612		SN0WM4N	Robot (JOI21_ho_t4)	C++14	0 / 100	35 ms	13652 KiB

Main

    #include <bits/stdc++.h>
    #include <ext/pb_ds/assoc_container.hpp>
    #include <ext/pb_ds/tree_policy.hpp>
    #define sort undefined_function // To use stable_sort instead sort 
    #define bpc __builtin_popcount
    #define ull unsigned long long
    #define ld double
    #define ll long long
    #define mp make_pair
    #define F first
    #define S second
     
    #pragma GCC optimize("O3")
     
    #ifdef LOCAL 
    	#include "debug.h"
    #else 
    	#define dbg(...) 0
    #endif
     
    using namespace __gnu_pbds;
    using namespace std;
     
    typedef tree<long long, null_type, less_equal<long long>,
        rb_tree_tag, tree_order_statistics_node_update> Tree;
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
     
    const ll INF = 9223372036854775807LL;
    const ll inf = 2147483647;
    const ll MOD = 1e9 + 7; //[998244353, 1e9 + 7, 1e9 + 13]
    const ld PI = acos(-1);
    const ll NROOT = 500;
     
    ll binpow(ll a, ll b, ll _MOD = -1) {
    	if (_MOD == -1)
    		_MOD = MOD;
    	ll res = 1;
    	for (; b; b /= 2, a *= a, a %= _MOD)
    		if (b & 1) res *= a, res %= _MOD;
    	return res;
    }
     
    void set_IO(string s) {
    #ifndef LOCAL
    	string in  = s +  ".in";
    	string out = s + ".out";
    	freopen(in.c_str(),  "r",  stdin);
    	freopen(out.c_str(), "w", stdout);
    #endif
    }
     
    bool dataOverflow(ll a, ll b) {return (log10(a) + log10(b) >= 18);}
    ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
    ll lcm(ll a, ll b) {return a * b / gcd(a, b);}
    ll ceil(ll a, ll b) {return (a + b - 1) / b;}
    ll invmod(ll a) {return binpow(a, MOD - 2);}
     
    int n, m;
    struct edge{
    	int b, c;
    	ll p;
    	edge(int _b, int _c, ll _p) {
    		b = _b;
    		c = _c;
    		p = _p;
    	}
    };
     
    vector<vector<edge>> g;
    vector<map<int, ll>> dis;
     
    int32_t main() {
    	ios_base::sync_with_stdio(0);
    	cin.tie(0); cout.tie(0);
     
    	cin >> n >> m;
    	g.resize(n + 1);
    	dis.resize(n + 1);
    	vector<map<int, ll>> val(n + 1);
    	vector<map<int, ll>> MAX(n + 1);
     
    	for (int i = 1; i <= m; i ++) {
    		int a, b, c; ll p;
    		cin >> a >> b >> c >> p;
    	
    		g[a].push_back(edge(b, c, p));
    		val[a][c] += p;
    		MAX[a][c] = max(MAX[a][c], p);
    	}
     
    	using T = pair<ll, pair<int, int>>;
    	priority_queue<T, vector<T>, greater<T>> q;
    	q.push({0, {1, 0}});
     
    	while (!q.empty()) {
    		ll d = q.top().F;
    		auto [x, c] = q.top().S;
    		q.pop();
     
    		if (dis[x].find(c) != dis[x].end())
    			continue;
    		dis[x][c] = d;
     
    		for (auto &y : g[x]) {
    			q.push({d + y.p, {y.b, 0}});
    			
    			if (c == 0) {
    				q.push({d + val[x][y.c] - y.p, {y.b, y.c}});
    				if (MAX[x][y.c] != val[x][y.c])	
    					q.push({d + val[x][y.c] - MAX[x][y.c], {y.b, 0}});	
    			} else {
    				if (c != y.c) {		
    					q.push({d + val[x][y.c] - y.p, {y.b, y.c}});
    					if (MAX[x][y.c] != y.p)
    					       	q.push({d + val[x][y.c] - MAX[x][y.c], {y.b, 0}});	
    				}
    			}
    		}
    	}
     
    	ll ans = INF;
    	for (auto &x : dis[n])
    		ans = min(ans, x.S);
     
    	dbg(dis[n]);
    	cout << (ans == INF ? -1 : ans) << '\n';
     
    	return 0;
    }

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:97:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   97 |       auto [x, c] = q.top().S;
      |            ^
Main.cpp:18:23: warning: statement has no effect [-Wunused-value]
   18 |      #define dbg(...) 0
      |                       ^
Main.cpp:125:6: note: in expansion of macro 'dbg'
  125 |      dbg(dis[n]);
      |      ^~~
Main.cpp: In function 'void set_IO(std::string)':
Main.cpp:47:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |      freopen(in.c_str(),  "r",  stdin);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:48:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |      freopen(out.c_str(), "w", stdout);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 34
• Subtask 2: 0 / 24
• Subtask 3: 0 / 42