Submission #199006

#	Time	Username	Problem	Language	Result	Execution time	Memory
199006		popovicirobert	City Mapping (NOI18_citymapping)	C++14	25 / 100	37 ms	10104 KiB

citymapping

#include "citymapping.h"
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int MAXN = 1000;

static ll dst[MAXN + 1][MAXN + 1];
static int qpos = 0;

inline ll get(int a, int b) {
    if(a == b) return 0;

    if(dst[a][b] == -1) {
        dst[a][b] = dst[b][a] = get_distance(a, b);
    }
    return dst[a][b];
}

inline int myrand(int md) {
    return (1LL * (1LL * rand() << 15) ^ rand()) % md;
}

void solve(vector <int> &nodes, int *a, int *b, int *w) {
    int sz = nodes.size();
    int nod = nodes[myrand(sz)];

    vector < pair <ll, int> > cur;
    for(auto it : nodes) {
        if(it != nod) {
            cur.push_back({get(nod, it), it});
        }
    }
    sort(cur.begin(), cur.end());

    vector < vector <int> > comps;
    for(auto it : cur) {
        int j = 0;
        while(j < min(2, (int)comps.size()) && get(nod, it.second) != get(nod, comps[j][0]) + get(comps[j][0], it.second)) {
            j++;
        }
        if(comps.size() == j) {
            comps.push_back(vector <int>());
        }
        comps[j].push_back(it.second);
        if(comps[j].size() == 1) {
            a[qpos] = nod;
            b[qpos] = it.second;
            w[qpos] = it.first;
            qpos++;
            //cerr << nod << " " << it.second << " " << it.first << "\n";
        }
    }

    for(auto &it : comps) {
        solve(it, a, b, w);
    }
}

void find_roads(int N, int Q, int A[], int B[], int W[]) {

    memset(dst, -1, sizeof(dst));
    srand(time(NULL));

    vector <int> nodes(N);
    iota(nodes.begin(), nodes.end(), 1);

    solve(nodes, A, B, W);

    /*cerr << qpos << "\n";
    for(i = 0; i < n - 1; i++) {

    }*/

	return ;
}

Compilation message (stderr)

citymapping.cpp: In function 'void solve(std::vector<int>&, int*, int*, int*)':
citymapping.cpp:43:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(comps.size() == j) {
            ~~~~~~~~~~~~~^~~~

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