Submission #1241984

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241984		thelegendary08	Wiring (IOI17_wiring)	C++17	13 / 100	16 ms	4936 KiB

wiring

#include "wiring.h"
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define mp make_pair
#define vb vector<bool>
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int,int>
#define vpii vector<pii>
#define f0r(i,n) for(int i = 0; i<n; i++)
#define FOR(i, k, n) for(int i = k; i<n; i++)
const int mxn = 1e5 + 5;
using namespace std;
vi par(mxn), sz(mxn);
int find(int x){
	if(x == par[x])return x;
	return par[x] = find(par[x]);
}
void unite(int a, int b){
	a = find(a); b = find(b);
	if(a == b)return;
	if(sz[a] < sz[b])swap(a,b);
	sz[a] += sz[b];
	par[b] = a;
}
long long min_total_length(std::vector<signed> r, std::vector<signed> b) {
	int n = r.size(); int m = b.size();
	vi v(n); vi w(m);
	f0r(i,n)v[i] = r[i];
	f0r(i, m)w[i] = b[i];
	/*
	vector<pair<int, pii>>edges;
	f0r(i, n){
		f0r(j, m){
			edges.pb(mp(abs(v[i] - w[j]), mp(i, j + n)));
		}
	}
	sort(edges.begin(), edges.end());
	f0r(i, n + m){
		par[i] = i; sz[i] = 1;
	}
	int ans = 0;
	f0r(i, edges.size()){
		int x = edges[i].second.first; int y = edges[i].second.second;
		if(sz[find(x)] == 1 || sz[find(y)] == 1){
			cout<<x<<' '<<y<<' '<<edges[i].first<<'\n';
			unite(x,y);
			ans += edges[i].first;
		}
	}
	return ans;
	*/
	
	int ans = 0;
	int mult = 1;
	f0r(i, n-1){
		ans += mult * (v[i+1] - v[i]);
		mult++;
	}
	ans += max(n, m) * (w[0] - v.back());
	mult = 1;
	for(int i = m-1; i>0; i--){
		ans += mult * (w[i] - w[i-1]);
		mult++;
	}
	return ans;
	return 0;
	
}

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