Submission #1307162

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307162		joesephdiver	Robot (JOI21_ho_t4)	C++20	0 / 100	121 ms	22412 KiB

Main

#include <algorithm>
#include <bits/stdc++.h>
#include <queue>
using namespace std;

template<class T> using V = vector<T>;

using ll  = long long;
using ull = unsigned long long;
using ld  = long double;

using pii = pair<int,int>;
using pll = pair<ll,ll>;

using vi = V<int>;


#define all(x)  begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define sz(x)   (int)((x).size())

#define pb  push_back
#define eb  emplace_back
#define mp  make_pair

#define rep(i,n)    for (int i = 0; i < (int)(n); ++i)
#define rep1(i,n)   for (int i = 1; i <= (int)(n); ++i)
#define forr(i,a,b) for (int i = (a); i <= (int)(b); ++i)
#define rfor(i,a,b) for (int i = (a); i >= (int)(b); --i)

const ll  INF64 = (1LL<<62) - 1;
const int INF   = 0x3f3f3f3f;    
const int MOD   = 1'000'000'007;

struct FastIO {
  FastIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.setf(std::ios::fixed); cout.precision(12);
  }
} fastio;

inline void setIO(const string& inFile, const string& outFile){
  if (!inFile.empty())  assert(freopen(inFile.c_str(), "r", stdin)  != nullptr);
  if (!outFile.empty()) assert(freopen(outFile.c_str(), "w", stdout) != nullptr);
}

inline void setIO(const string& base){
  setIO(base + ".in", base + ".out");
}

template <class T, class U>
struct PairHash {
    std::size_t operator()(const std::pair<T, U>& p) const noexcept {
        std::size_t h1 = std::hash<T>{}(p.first);
        std::size_t h2 = std::hash<U>{}(p.second);
        return h1 ^ (h2 + 0x9e3779b9 + (h1 << 6) + (h1 >> 2));
    }
};

template<class T> inline bool chmin(T& a, const T& b){ if(b < a){ a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, const T& b){ if(a < b){ a = b; return true; } return false; }

template<class T> inline T ceil_div(T a, T b){
  return (a>=0 ? (a + b - 1)/b : a/b);
}
template<class T> inline T floor_div(T a, T b){
  return (a>=0 ? a/b : (a - b + 1)/b);
}

template<class T> inline T clampv(T x, T lo, T hi){ return x < lo ? lo : (x > hi ? hi : x); }

template<class T> string to_str(const T& x){ std::ostringstream os; os << x; return os.str(); }

ll modpow(ll a, ll e, ll m=MOD){
  ll r = 1; a %= m; while(e){ if(e&1) r = (__int128)r*a % m; a = (__int128)a*a % m; e >>= 1; }
  return r;
}

template<class T>
vector<int> compress(const vector<T>& a, vector<T>* values_out=nullptr){
  vector<T> v = a; sort(all(v)); v.erase(unique(all(v)), v.end());
  if(values_out) *values_out = v;
  vector<int> id(a.size());
  rep(i, a.size()) id[i] = (int)(lower_bound(all(v), a[i]) - v.begin());
  return id;
}

template<class T> istream& operator>>(istream& is, vector<T>& v){ for (auto& x : v) is >> x; return is; }
template<class T> ostream& operator<<(ostream& os, const vector<T>& v){
  for (int i = 0; i < sz(v); ++i) os << v[i] << (i+1==sz(v) ? "" : " ");
  return os;
}

struct DSU {
    V<int> e; void init(int N) { e = V<int>(N,-1); }
    int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); } 
    bool sameSet(int a, int b) { return get(a) == get(b); }
    int size(int x) { return -e[get(x)]; }
    bool unite(int x, int y) {
        x = get(x), y = get(y); if (x == y) return 0;
        if (e[x] > e[y]) swap(x,y);
        e[x] += e[y]; e[y] = x; return 1;
    }
};

const int dx4[4] = {1,0,-1,0}, dy4[4] = {0,1,0,-1};
const int dx8[8] = {1,1,0,-1,-1,-1,0,1}, dy8[8] = {0,1,1,1,0,-1,-1,-1};
const int kx[8]  = {1,2,2,1,-1,-2,-2,-1}, ky[8] = {2,1,-1,-2,-2,-1,1,2};

struct edge{
	ll dest, color, cost;
	bool operator>(edge other) const {
		return cost > other.cost;
	}
};

int main(){
	int N, M;
	cin >> N >> M;
	V<V<edge>> adj(N);
	rep(i, M){
		ll a, b, c, p;
		cin >> a >> b >> c >> p;
		a--, b--;
		adj[a].pb({b, c, p});
		adj[b].pb({a, c, p});
	}
	priority_queue<edge, vector<edge>, greater<edge>> q;
	q.push({0, 0, 0});
	vi dist(N, -1);
	while(!q.empty()){
		auto f = q.top();
		q.pop();
		if(dist[f.dest] != -1) continue;
		//cout << "visiting: " << f.dest << ", cost: " << f.cost << endl;
		//increment cost later
		dist[f.dest] = f.cost;
		//iterate over each thing, check how many have each color
		//if >1 have some color, check if cheaper to change that or change everything else, then perform and continue
		
		//keeps count, sum
		unordered_map<int, pii> colors;
		for(edge& e: adj[f.dest]){
			colors.try_emplace(e.color, 0, 0);
			colors[e.color].first++;
			colors[e.color].second += e.cost;
		}
		for(edge& e: adj[f.dest]){
			if(colors[e.color].first == 1) q.push({e.dest, e.color, f.cost});
			//more than one of this color
			else{
				//if cost exceeds sum-this, pay sum-this
				q.push({e.dest, e.color, f.cost+min(e.cost, colors[e.color].second-e.cost)});
			}
		}
	}
	cout << dist[N-1] << endl;
}

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