Submission #147500

#	Time	Username	Problem	Language	Result	Execution time	Memory
147500		JovanK26	City Mapping (NOI18_citymapping)	C++14	0 / 100	110 ms	7780 KiB

citymapping

#include "citymapping.h"
#include<bits/stdc++.h>
using namespace std;
struct edge
{
    int a;
    int b;
    int w;
};
vector<edge> edg;
bool cmp(edge i,edge j)
{
    return i.w<j.w;
}
bool vis[1001][1001];
int prt[1001];
int sz[1001];
int findd(int x)
{
    while(prt[x]!=x)
    {
        x=prt[x];
    }
    return x;
}
void unionn(int x,int y)
{
    x=findd(x);
    y=findd(y);
    if(sz[x]<sz[y])swap(x,y);
    prt[y]=x;
    sz[x]+=sz[y];
}
void find_roads(int N, int Q, int A[], int B[], int W[]) {
    int br=0;
    for(int i=0;i<=N;i++)
    {
        prt[i]=i;
        sz[i]=1;
    }
    for(int i=1;i<=N;i++)
    {
        for(int j=1;j<=N;j++)
        {
            if(i==j)continue;
            if(vis[i][j] || vis[j][i])continue;
            vis[i][j]=1;
            vis[j][i]=1;
            long long temp=get_distance(i,j);
            edge tmp;
            tmp.a=i;
            tmp.b=j;
            tmp.w=temp;
            edg.push_back(tmp);
        }
    }
    sort(edg.begin(),edg.end(),cmp);
    for(int i=0;i<edg.size();i++)
    {
        if(findd(edg[i].a)==findd(edg[i].b))
        {
            unionn(edg[i].a,edg[i].b);
            A[br]=edg[i].a;
            B[br]=edg[i].b;
            W[br]=edg[i].w;
            br++;
        }
    }
	return;
}

Compilation message (stderr)

citymapping.cpp: In function 'void find_roads(int, int, int*, int*, int*)':
citymapping.cpp:58:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<edg.size();i++)
                 ~^~~~~~~~~~~

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