Submission #486596

#	Time	Username	Problem	Language	Result	Execution time	Memory
486596		socho	Robot (JOI21_ho_t4)	C++14	100 / 100	1672 ms	104776 KiB

Main

/*
	Implementation of Aruj's idea of splitting cases into "forcibly recolour others" and "anything is ok"
*/
#include <bits/stdc++.h>
using namespace std;
void fast() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
}
void ran() {
	srand(chrono::steady_clock::now().time_since_epoch().count());
}
long long get_rand() {
	long long a = rand();
	long long b = rand();
	return a * (RAND_MAX + 1ll) + b;
}
void usaco() {
	freopen("problem.in", "r", stdin); 
	freopen("problem.out", "w", stdout);
}
template<typename T>
using min_pq = priority_queue<T, vector<T>, greater<T>>;
#define endl '\n'
// #define double long double
#define int long long
// const int MOD = 1000 * 1000 * 1000 + 7;
// const int MOD = 998244353;
// #define cerr if(0) cerr
#define debug(x) cerr << #x << ": " << x << endl;
 
int n, m;
const int MXN = 100005;
const int MXM = 200005;
int a[MXM], b[MXM], colour[MXM], price[MXM];
vector<pair<int, int>> adj[MXN];
map<int, int> adj_sum[MXN];
map<int, vector<pair<int, int>>> adjbycolour[MXN];
 
map<pair<int, int>, int> dist;
 
int getdist(int no, int co) {
	pair<int, int> tr = {no, co};
	auto f = dist.find(tr);
	if (f == dist.end()) return LLONG_MAX / 4;
	return f->second;
}
 
void setdist(int no, int co, int to) {
	dist[{no, co}] = to;
}
 
signed main() {
 
	ran(); fast();
 
	cin >> n >> m;
	for (int i=1; i<=m; i++) {
		cin >> a[i] >> b[i] >> colour[i] >> price[i];
		adj[a[i]].push_back({i, 1}); // connect it to the other side
		adj[b[i]].push_back({i, 0}); // connect it to the other side
		adj_sum[a[i]][colour[i]]+=price[i];
		adj_sum[b[i]][colour[i]]+=price[i];
		adjbycolour[a[i]][colour[i]].push_back({i, 1});
		adjbycolour[b[i]][colour[i]].push_back({i, 0});
	}
	
	min_pq<pair<int, pair<int, int>>> proc;
	proc.push({0, {1, -1}});
	
	while (!proc.empty()) {
		
		auto f = proc.top(); proc.pop();
		int di = f.first, no = f.second.first, co = f.second.second;
		
		if (getdist(no, co) < di) continue;
        setdist(no, co, di);
		// cout << no << " " << co << ": " << di << endl;
		
		if (co == -1) {
			// go anywhere tbh
			for (auto x: adj[no]) {
				int edge_num = x.first, ot = x.second;
				int other = a[edge_num];
				if (ot == 1) other = b[edge_num];
				// either recolour this one edge, paying price[edge_num]
				int od = getdist(other, -1); // you'll end somewhere without restriction
				if (di + price[edge_num] < od) {
					setdist(other, -1, di + price[edge_num]);
					proc.push({di + price[edge_num], {other, -1}});
				}
				// or recolour this edge, but pay later by forcing the same colour to be used next time
				od = getdist(other, colour[edge_num]);
				if (di < od) {
					setdist(other, colour[edge_num], di);
					proc.push({di, {other, colour[edge_num]}});
				}
				// or recolour all the other edges of this colour, paying the price here
				od = getdist(other, -1);
				int cost = adj_sum[no][colour[edge_num]] - price[edge_num];
				if (cost + di < od) {
					setdist(other, -1, cost + di);
					proc.push({cost+di, {other, -1}});
				}
			}
		}
		else {
			// you have agreed to take only certain coloured edges, and also to not recolour only the edge you take out of here
			// ie you must recolour all other edges of whatever colour you take
			int sm = adj_sum[no][co];
			for (auto x: adjbycolour[no][co]) {
				int edge_num = x.first, ot = x.second;
				int other = a[edge_num];
				if (ot == 1) other = b[edge_num];
				int od = sm - price[edge_num] + di;
				int curr = getdist(other, -1);
				if (od < curr) {
					setdist(other, -1, od);
					proc.push({od, {other, -1}});
				}
			}
		}
		
	}
	
	int res = getdist(n, -1);
	if (res == LLONG_MAX / 4) cout << -1 << endl;
	else cout << res << endl;
	
}

Compilation message (stderr)

Main.cpp: In function 'void usaco()':
Main.cpp:18:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |  freopen("problem.in", "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:19:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |  freopen("problem.out", "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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