Submission #113478

#	Time	Username	Problem	Language	Result	Execution time	Memory
113478		E869120	Wiring (IOI17_wiring)	C++14	100 / 100	664 ms	142820 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;

long long N, M, A[200009], B[200009], SA[200009], SB[200009], dp[1400009];
vector<pair<int, int>> G, G2, X[100009], Y[100009], R[200009];
vector<pair<int, long long>> Z[1400009];

void prints() {
	cout << "--- Data of Z ---" << endl;
	for (int i = 0; i < G.size(); i++) {
		for (int j = 0; j < Z[i].size(); j++) {
			cout << i << " -> " << Z[i][j].first << ", Weight = " << Z[i][j].second << endl;
		}
	}
	cout << endl;
}

void printg() {
	cout << "--- Data of G ---" << endl;
	for (int i = 0; i < G.size(); i++) printf("#% 3d: (% 3d, % 3d)\n", i, G[i].first, G[i].second);
	cout << endl;
}

long long solve() {
	for (int i = 0; i < N; i++) SA[i + 1] = SA[i] + A[i];
	for (int i = 0; i < M; i++) SB[i + 1] = SB[i] + B[i];
	
	// 調和点の追加
	for (int i = 0; i < N; i++) {
		int pos1 = lower_bound(A, A + N, A[i] + 1) - A;
		int pos2 = lower_bound(B, B + M, A[i] + 1) - B;
		G.push_back(make_pair(pos1, pos2));
		for (int j = 0; j <= 1; j++) { for (int k = -1; k <= 1; k++) { G.push_back(make_pair(i + j, pos2 + k)); } }
	}
	for (int i = 0; i < M; i++) {
		int pos1 = lower_bound(A, A + N, B[i] + 1) - A;
		int pos2 = lower_bound(B, B + M, B[i] + 1) - B;
		G.push_back(make_pair(pos1, pos2));
		for (int j = 0; j <= 1; j++) { for (int k = -1; k <= 1; k++) { G.push_back(make_pair(pos1 + k, i + j)); } }
	}
	G.push_back(make_pair(0, 0));
	G.push_back(make_pair(N, M));
	
	for (int i = 0; i < G.size(); i++) {
		if (G[i].first < 0 || G[i].second < 0 || G[i].first > N || G[i].second > M) continue;
		if ((G[i].first == 0 || G[i].second == 0) && G[i].first + G[i].second != 0) continue;
		G2.push_back(G[i]);
	}
	G = G2;
	sort(G.begin(), G.end());
	G.erase(unique(G.begin(), G.end()), G.end());
	
	//printg();
	
	for (int i = 0; i < G.size(); i++) {
		X[G[i].first].push_back(make_pair(G[i].second, i));
		Y[G[i].second].push_back(make_pair(G[i].first, i));
		R[G[i].first - G[i].second + M].push_back(make_pair(G[i].first, i));
	}
	for (int i = 0; i <= N; i++) {
		for (int j = 0; j < (int)X[i].size() - 1; j++) {
			if (X[i][j + 1].first - X[i][j].first != 1) continue;
			Z[X[i][j].second].push_back(make_pair(X[i][j + 1].second, abs(A[i - 1] - B[X[i][j + 1].first - 1])));
		}
	}
	//prints();
	for (int i = 0; i <= M; i++) {
		for (int j = 0; j < (int)Y[i].size() - 1; j++) {
			if (Y[i][j + 1].first - Y[i][j].first != 1) continue;
			Z[Y[i][j].second].push_back(make_pair(Y[i][j + 1].second, abs(B[i - 1] - A[Y[i][j + 1].first - 1])));
		}
	}
	//prints();
	for (int i = -M; i <= N; i++) {
		for (int j = 0; j < (int)R[i + M].size() - 1; j++) {
			int cx = i + M;
			long long B1 = SA[R[cx][j + 1].first] - SA[R[cx][j].first];
			long long B2 = SB[R[cx][j + 1].first - i] - SB[R[cx][j].first - i];
			Z[R[cx][j].second].push_back(make_pair(R[cx][j + 1].second, abs(B1 - B2)));
		}
	}
	//prints();
	
	for (int i = 0; i < (int)G.size(); i++) dp[i] = (1LL << 60);
	dp[0] = 0;
	for (int i = 0; i < (int)G.size(); i++) {
		for (int j = 0; j < (int)Z[i].size(); j++) dp[Z[i][j].first] = min(dp[Z[i][j].first], dp[i] + Z[i][j].second);
	}
	return dp[G.size() - 1];
}

long long min_total_length(vector<int> r, vector<int> b) {
	N = r.size(); M = b.size();
	for (int i = 0; i < N; i++) A[i] = r[i];
	for (int i = 0; i < M; i++) B[i] = b[i];
	
	return solve();
}

Compilation message (stderr)

wiring.cpp: In function 'void prints()':
wiring.cpp:11:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < G.size(); i++) {
                  ~~^~~~~~~~~~
wiring.cpp:12:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < Z[i].size(); j++) {
                   ~~^~~~~~~~~~~~~
wiring.cpp: In function 'void printg()':
wiring.cpp:21:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < G.size(); i++) printf("#% 3d: (% 3d, % 3d)\n", i, G[i].first, G[i].second);
                  ~~^~~~~~~~~~
wiring.cpp: In function 'long long int solve()':
wiring.cpp:45:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < G.size(); i++) {
                  ~~^~~~~~~~~~
wiring.cpp:56:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < G.size(); i++) {
                  ~~^~~~~~~~~~

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