Submission #429288

#	Time	Username	Problem	Language	Result	Execution time	Memory
429288		Dremix10	Wiring (IOI17_wiring)	C++17	0 / 100	1 ms	204 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
#define F first
#define S second
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#ifdef dremix
    #define p(x) cerr<<#x<<" = "<<x<<endl;
    #define p2(x,y) cerr<<#x<<", "<<#y<<" = {"<<x<<", "<<y<<"}"<<endl;
    #define pp(x) cerr<<#x<<" = "<<"("<<x.F<<" - "<<x.S<<")"<<endl;
    #define pv(x) cerr<<#x<<" = "<<"{";for(auto y : x)cerr<<y<<", ";cerr<<"}"<<endl;
    #define ppv(x) cerr<<#x<<" = "<<"{";for(auto y : x)cerr<<y.F<<"-"<<y.S<<", ";cerr<<"}"<<endl;
#else
    #define p(x)
    #define p2(x,y)
    #define pp(x)
    #define pv(x)
    #define ppv(x)
#endif
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int maxp = 22;
const ld EPS = 1e-9;
const ll INF = 1e18;
const int MOD = 1e9+7;
const int N = 3e5+1;

struct ano{
    int x,y,z;
    bool operator<(const ano &x)const{
        return z<x.z;
    }
};

int par[N],siz[N],tot;

int find(int x){
    return (par[x]==x) ? x : par[x] = find(par[x]);
}

bool join(int x, int y){
    x = find(x);
    y = find(y);
    if(siz[x]>1 && siz[y]>1)return 0;
    par[y] = x;
    if(siz[y]==1)tot--;
    if(siz[x]==1)tot--;
    siz[x] += siz[y];
    return 1;
}

long long min_total_length(vector<int> a, vector<int> b) {
    int n = a.size();
    int m = b.size();
    int i,j;

    ll ans = 0;

    vector<ano> arr;

    for(i=0;i<n;i++)
    for(j=0;j<m;j++){
        arr.push_back({i,j+n,abs(a[i]-b[j])});
    }
    sort(all(arr));

    for(i=0;i<n+m;i++){
        par[i] = i;
        siz[i] = 1;
    }
    tot = n+m;
    int pos = 0;

    while(tot>0 && pos<arr.size()){
        if(join(arr[pos].x,arr[pos].y)){
            ans += arr[pos].z;
            p2(arr[pos].x,arr[pos].y)
            p2(arr[pos].z,ans)
        }
        pos++;
    }

    return ans;

    /*
    g++ grader.cpp wiringSub1.cpp -Ddremix

    */
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:79:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<ano>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     while(tot>0 && pos<arr.size()){
      |                    ~~~^~~~~~~~~~~

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