Submission #590013

#	Time	Username	Problem	Language	Result	Execution time	Memory
590013		AlesL0	Wiring (IOI17_wiring)	C++17	0 / 100	262 ms	262144 KiB

wiring

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct edge {
    ll len, red, blue;
};

bool cmp(edge a, edge b){
    return (a.len < b.len);
}

const ll INF = 1e10;

long long min_total_length(std::vector<int> r, std::vector<int> b){
    ll n = r.size(), m = b.size();
    vector <edge> e;
    for (int i = 0; i < r.size(); i++){
        for (int j = 0; j < b.size(); j++)e.push_back({abs(r[i]-b[j]), i, j});
    }
    vector <bool> bred(r.size(), 0), bblue(b.size(), 0);
    ll s = 0;
    sort(e.begin(), e.end(), cmp);
    for (auto x : e){
        if (!bred[x.red] && !bblue[x.blue]){
            bred[x.red] = 1; bblue[x.blue] = 1;
            s += x.len;
        }
    }
    vector <ll> closestr(n, INF), closestb(m, INF);
    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++){
            closestr[i] = min(closestr[i], (long long)abs(r[i]-b[j]));
            closestb[j] = min(closestb[j], (long long)abs(r[i]-b[j]));
        }
    }
    if (n > m){
        for (int i = 0; i < r.size(); i++)if (!bred[i])s += closestr[i];
    }
    else {
        for (int i = 0; i < b.size(); i++)if (!bblue[i])s += closestb[i];
    }
    return s;
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:20:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for (int i = 0; i < r.size(); i++){
      |                     ~~^~~~~~~~~~
wiring.cpp:21:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |         for (int j = 0; j < b.size(); j++)e.push_back({abs(r[i]-b[j]), i, j});
      |                         ~~^~~~~~~~~~
wiring.cpp:40:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         for (int i = 0; i < r.size(); i++)if (!bred[i])s += closestr[i];
      |                         ~~^~~~~~~~~~
wiring.cpp:43:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |         for (int i = 0; i < b.size(); i++)if (!bblue[i])s += closestb[i];
      |                         ~~^~~~~~~~~~

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