Submission #246227

#	Time	Username	Problem	Language	Result	Execution time	Memory
246227		SamAnd	City Mapping (NOI18_citymapping)	C++17	32 / 100	6 ms	512 KiB

citymapping

#include "citymapping.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;

const int MAXN = 1003;
const ll INF = 1000000009000000009;

int n;

ll d1[MAXN];
ll dminx[MAXN];

bool so(const int x, const int y)
{
    return d1[x] < d1[y];
}

void solv2(int A[], int B[], int W[])
{
    for (int x = 2; x <= n; ++x)
    {
        d1[x] = get_distance(1, x);
    }

    ll minu = INF;
    int minx;
    for (int x = 2; x <= n; ++x)
    {
        if (d1[x] < minu)
        {
            minu = d1[x];
            minx = x;
        }
    }

    for (int x = 1; x <= n; ++x)
    {
        if (x == minx)
            continue;
        dminx[x] = get_distance(minx, x);
    }

    vector<int> l, r;
    for (int x = 1; x <= n; ++x)
    {
        if (x == 1)
            continue;
        if (d1[x] < dminx[x])
            l.push_back(x);
        else
            r.push_back(x);
    }

    sort(all(l), so);
    sort(all(r), so);

    int m = 0;
    for (int i = 0; i < sz(l); ++i)
    {
        int x = l[i];
        if (i == 0)
        {
            A[m] = 1;
            B[m] = x;
            W[m] = d1[x];
        }
        else
        {
            A[m] = l[i - 1];
            B[m] = x;
            W[m] = d1[x] - d1[l[i - 1]];
        }
        m++;
    }
    for (int i = 0; i < sz(r); ++i)
    {
        int x = r[i];
        if (i == 0)
        {
            A[m] = 1;
            B[m] = x;
            W[m] = d1[x];
        }
        else
        {
            A[m] = r[i - 1];
            B[m] = x;
            W[m] = d1[x] - d1[r[i - 1]];
        }
        m++;
    }
}

void find_roads(int N, int Q, int A[], int B[], int W[])
{
    n = N;
    if (Q == 12000)
    {
        solv2(A, B, W);
    }
	return;
}

/*
4 12000 4
2 1 100
1 3 5
3 4 1
*/

Compilation message (stderr)

citymapping.cpp: In function 'void solv2(int*, int*, int*)':
citymapping.cpp:44:9: warning: 'minx' may be used uninitialized in this function [-Wmaybe-uninitialized]
         if (x == minx)
         ^~

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