Submission #710726

#	Time	Username	Problem	Language	Result	Execution time	Memory
710726		Clan328	Wiring (IOI17_wiring)	C++17	0 / 100	191 ms	66976 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>

using namespace std;

#define pb push_back

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;

vvi G, W;

vi p, visited;
vector<vector<ll>> dp;

void dfs(int v, int par) {
	visited[v] = true;
	p[v] = par;
	for (auto u : G[v]) {
		if (u == par) continue;
		if (visited[u]) continue;
		dfs(u, v);
	}
}

ll getDP(int v, bool needsGroup) {
	if (dp[v][needsGroup] != -1) return dp[v][needsGroup];

	if (p[v] != -1) {
		if (G[v].size() == 1 && needsGroup) {
			dp[v][needsGroup] = INT_MAX;
			return dp[v][needsGroup];
		} else if (G[v].size() == 1 && !needsGroup) {
			dp[v][needsGroup] = 0;
			return dp[v][needsGroup];
		}
	}

	ll res = 0;
	ll minX = INT_MAX;
	for (int i = 0; i < G[v].size(); i++) {
		int u = G[v][i];
		if (u == p[v]) continue;
		
		if (!needsGroup) {
			res += min(getDP(u, 0)+W[v][i], getDP(u, 1));
		}
		else {
			if (getDP(u, 1) == INT_MAX) {
				res += getDP(u, 0)+W[v][i];
				minX = 0;
			} else {
				res += getDP(u, 1);
				minX = min(minX, getDP(u, 0)+W[v][i] - getDP(u, 1));
			}
		}
	}

	if (needsGroup) {
		res += minX;
	}

	dp[v][needsGroup] = res;

	return res;
}

ll min_total_length(vi r, vi b) {
	int n = r.size(), m = b.size();

	vi a;
	vi left(n+m), right(n+m);
	int lastR = -1, lastB = -1;
	int idxA = 0, idxB = 0;
	while (idxA < n || idxB < m) {
		if (idxA < n && (idxB >= m || r[idxA] < b[idxB])) {
			left[idxA+idxB] = lastB;
			lastR = idxA+idxB;//r[idxA];
			a.pb(r[idxA]);
			idxA++;
		} else {
			left[idxA+idxB] = lastR;
			lastB = idxA+idxB;//b[idxB];
			a.pb(b[idxB]);
			idxB++;
		}
	}

	lastR = -1, lastB = -1;
	idxA = n-1, idxB = m-1;
	while (idxA >= 0 || idxB >= 0) {
		if (idxA >= 0 && (idxB < 0 || r[idxA] > b[idxB])) {
			right[idxA+idxB+1] = lastB;
			lastR = idxA+idxB+1;//r[idxA];
			idxA--;
		} else {
			right[idxA+idxB+1] = lastR;
			lastB = idxA+idxB+1;//b[idxB];
			idxB--;
		}
	}

	G = vvi(n+m);
	W = vvi(n+m);

	map<pair<int, int>, int> doubleEdge;

	for (int i = 0; i < n+m; i++) {
		int d1 = left[i] != -1? a[i]-a[left[i]] : INT_MAX;
		int d2 = right[i] != -1? a[right[i]]-a[i] : INT_MAX;
		if ((d1 <= d2) && left[i] != -1 && doubleEdge.count({i, left[i]}) == 0) {
			G[i].pb(left[i]);
			W[i].pb(a[i]-a[left[i]]);
			G[left[i]].pb(i);
			W[left[i]].pb(a[i]-a[left[i]]);

			doubleEdge[{i, left[i]}] = doubleEdge[{left[i], i}] = 1;
		}
		// cout << d1 << " " << d2 << endl;
		if ((d2 <= d1) &&right[i] != -1 && doubleEdge.count({i, right[i]}) == 0) {
			G[i].pb(right[i]);
			W[i].pb(a[right[i]]-a[i]);
			G[right[i]].pb(i);
			W[right[i]].pb(a[right[i]]-a[i]);

			doubleEdge[{i, right[i]}] = doubleEdge[{right[i], i}] = 1;
		}
	}

	int k = 0;
	for (int i = 0; i < n+m; i++) {
		for (int j = 0; j < G[i].size(); j++) {
			if (i >= G[i][j]) continue;
			// cout << i << " " << G[i][j] << " " << W[i][j] << endl;
			k += W[i][j];
		}
	}

	// return k;

	// for (int i = 0; i < n+m; i++) cout << right[i] << " ";
	// 	cout << endl;

	p = vi(n+m);
	visited = vi(n+m);
	for (int i = 0; i < n+m; i++) {
		if (visited[i]) continue;
		if (G[i].size() == 1) {
			dfs(i, -1);
		}
	}

	dp = vector<vector<ll>>(n+m, vector<ll>(2, -1));
		
	int res = 0;
	for (int i = 0; i < n+m; i++) {
		if (dp[i][1] != -1) continue;
		if (G[i].size() == 1) {
			res += getDP(i, 1);
			// cout << getDP(i, 1) << endl;
		}
	}

	return res;
}

Compilation message (stderr)

wiring.cpp: In function 'll getDP(int, bool)':
wiring.cpp:42:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |  for (int i = 0; i < G[v].size(); i++) {
      |                  ~~^~~~~~~~~~~~~
wiring.cpp: In function 'll min_total_length(vi, vi)':
wiring.cpp:133:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |   for (int j = 0; j < G[i].size(); j++) {
      |                   ~~^~~~~~~~~~~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 13
• Subtask 3: 0 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 45