Submission #485510

#	Time	Username	Problem	Language	Result	Execution time	Memory
485510		socho	Robot (JOI21_ho_t4)	C++14	0 / 100	1274 ms	129812 KiB

Main

/*
	Going for full conversion
	 * first idea: "node" retrievable using boolean number of states, since each road will have two sides. represent a => 0 and b => 1
	 * this is still NM-ish as every road is checked N times from each place?
	 * now we will consider the cases.
	 * and different-colour pairs are the same options every single time anyway
	 * so we can split the roads connected to each node by their colour
	 * for the first time we visit a node, just try going to every other place
	 * every future time, only consider going to roads of the same colour (of course, if you've come to this node and colour pair before then don't go to the same colour ones either)
*/
#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];
int dist[2][MXM][2];
map<int, int> adj_count[MXN];
map<int, int> adj_sum[MXN];
map<int, bool> visited[MXN]; // for a node, colour, has this combo happened?
bool visit[MXN]; // has the node itself been visited before?
map<int, vector<pair<int, int>>> adjbycolour[MXN];

signed main() {

	ran(); fast();

	for (int i=0; i<2; i++) for (int j=0; j<MXM; j++) dist[i][j][0] = dist[i][j][1] = LLONG_MAX / 4;

	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_count[a[i]][colour[i]]++;
		adj_count[b[i]][colour[i]]++;
		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});
	}
	
	// initially at node 1, previous road '0', was not changed, price is 0
	
	b[0] = 1; // just to setup the initial
	
	min_pq<pair<int, pair<pair<int, int>, int>>> process;
	process.push({0, {{1, 0}, 0}}); // node (a or b), prevroad, didwechange
	
	int ans = LLONG_MAX;
	
	while (!process.empty()) {
		
		auto x = process.top(); process.pop();
		int di = x.first;
		int prevroad = x.second.first.second;
		int node = x.second.first.first;
		int onode = node;
		
		if (node == 0) {
			node = a[prevroad];
		}
		else {
			node = b[prevroad];
		}
		
		int waschanged = x.second.second;
		
		if (node == n) {
			ans = min(ans, di);
		}
		
		// cout << node << ' ' << prevroad << " " << waschanged << ": " << di << endl;
		if (dist[onode][prevroad][waschanged] < di) {
			continue;
		}
		
		dist[onode][prevroad][waschanged] = di;
		
		// here we must decide. first, if this node has not been visited at all before, we must do the entire process anyway so:
		
		if (!visit[node]) {
			visit[node] = true; // now it has!
			for (auto x: adj[node]) {
				int road = x.first, other = x.second;
				// what is the cost of going there?
				if (road == prevroad) continue; // don't go back the previous road, why would you?
				if (adj_count[node][colour[road]] == 1) {
					// then it's free!
					if (di < dist[other][road][0]) {
						process.push({di, {{other, road}, 0}});
						dist[other][road][0] = di;
					}
				}
				else {
					// there's a lot of these roads with this colour, so we must change something
					int cost_change = price[road]; // what is the cost of changing this road, so we can use it?
					int cost_others = adj_sum[node][colour[road]] - cost_change; // what is the cost of changing all the other roads?
					if (colour[prevroad] == colour[road]) {
						// the old road is one of those other roads
						if (waschanged) {
							// old road colour already changed, don't change again!
							cost_others -= price[prevroad];
						}
					}
					
					assert(cost_change >= 0);
					assert(cost_others >= 0);
					
					// now we consider changing this road:
					
					if (di + cost_change < dist[other][road][1]) {
						process.push({di + cost_change, {{other, road}, 1}});
						dist[other][road][1] = di + cost_change;
					}
					// or changing all other roads:
					if (di + cost_others < dist[other][road][0]) {
						process.push({di + cost_others, {{other, road}, 0}});
						dist[other][road][0] = di + cost_others;
					}
				}
			}
		}
		else {
			// continue;
			// it's been visited before. has this colour combo been visited before?
			if (!visited[node][colour[prevroad]]) {
				// no, so propagate to adjacents by colour only!
				visited[node][colour[prevroad]] = true; 
				
				for (auto x: adjbycolour[node][colour[prevroad]]) {
					int road = x.first, other = x.second;
					// what is the cost of going there?
					if (road == prevroad) continue; // don't go back the previous road, why would you?
					if (adj_count[node][colour[road]] == 1) {
						// then it's free!
						if (di < dist[other][road][0]) {
							process.push({di, {{other, road}, 0}});
							dist[other][road][0] = di;
						}
					}
					else {
						// there's a lot of these roads with this colour, so we must change something
						int cost_change = price[road]; // what is the cost of changing this road, so we can use it?
						int cost_others = adj_sum[node][colour[road]] - cost_change; // what is the cost of changing all the other roads?
						if (colour[prevroad] == colour[road]) {
							// the old road is one of those other roads
							if (waschanged) {
								// old road colour already changed, don't change again!
								cost_others -= price[prevroad];
							}
						}
						
						assert(cost_change >= 0);
						assert(cost_others >= 0);
						
						// now we consider changing this road:
						
						if (di + cost_change < dist[other][road][1]) {
							process.push({di + cost_change, {{other, road}, 1}});
							dist[other][road][1] = di + cost_change;
						}
						// or changing all other roads:
						if (di + cost_others < dist[other][road][0]) {
							process.push({di + cost_others, {{other, road}, 0}});
							dist[other][road][0] = di + cost_others;
						}
					}
				}
				
			}
			else {
				// yes, so ignore :(
			}
		}
		
	}
	
	if (ans == LLONG_MAX) cout << -1 << endl;
	else cout << ans << endl;

}

Compilation message (stderr)

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

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