Submission #1236085

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236085		MarwenElarbi	City Mapping (NOI18_citymapping)	C++20	0 / 100	38 ms	8256 KiB

citymapping

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

#define fi first
#define se second
int parent[1005];
int find(int x){
    if(x==parent[x]) return x;
    return parent[x]=find(parent[x]);
}
void joinset(int x,int y){
    x=find(x);
    y=find(y);
    parent[x]=y;
}
bool sameset(int x,int y){
    return find(x) == find(y) ; 
}
void find_roads(int N, int Q, int A[], int B[], int W[]) {
    long long dis[N+1][N+1];
    int k=0;
    for (int i = 1; i <= N; ++i)
    {
        parent[i]=i;
        for (int j = i+1; j <= N; ++j)
        {
            dis[j][i] = dis[i][j] = get_distance(i,j);
        }
    }
    for (int i = 1; i <= N; ++i)
    {
        pair<long long,int> cur={1e18,-1};
        for (int j = 1; j <= N; ++j)
        {
            if(i==j) continue;
            if(sameset(i,j)) continue;
            cur=min(cur,{dis[i][j],j});
        }
        if(cur == make_pair(1ll*1000000000000000000,-1)) continue;
        joinset(i,cur.se);
        A[k]=i;
        B[k]=cur.se;
        W[k]=cur.fi;
        k++;
    }
    return;
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 16
• Subtask 3: 0 / 13
• Subtask 4: 0 / 19
• Subtask 5: 0 / 43