oj.uz

Submission #199006

# Submission time Handle Problem Language Result Execution time Memory
199006 2020-01-28T16:04:24 Z popovicirobert City Mapping (NOI18_citymapping) C++14
25 / 100
 37 ms 10104 KB 
#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

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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 8444 KB Correct: 23600 out of 500000 queries used.
2 Correct 17 ms 8568 KB Correct: 41462 out of 500000 queries used.
3 Correct 34 ms 10104 KB Correct: 151839 out of 500000 queries used.
4 Correct 31 ms 9976 KB Correct: 132074 out of 500000 queries used.
5 Correct 23 ms 9208 KB Correct: 68750 out of 500000 queries used.

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 8444 KB Correct: 23600 out of 500000 queries used.
2 Correct 17 ms 8568 KB Correct: 41462 out of 500000 queries used.
3 Correct 34 ms 10104 KB Correct: 151839 out of 500000 queries used.
4 Correct 31 ms 9976 KB Correct: 132074 out of 500000 queries used.
5 Correct 23 ms 9208 KB Correct: 68750 out of 500000 queries used.
6 Correct 15 ms 8440 KB Correct: 23906 out of 500000 queries used.
7 Correct 15 ms 8568 KB Correct: 35451 out of 500000 queries used.
8 Correct 30 ms 9592 KB Correct: 120882 out of 500000 queries used.
9 Correct 37 ms 10104 KB Correct: 151296 out of 500000 queries used.
10 Correct 18 ms 8696 KB Correct: 42342 out of 500000 queries used.

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 8440 KB Too many calls to get_distance().
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 8440 KB Too many calls to get_distance().
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 8444 KB Correct: 23600 out of 500000 queries used.
2 Correct 17 ms 8568 KB Correct: 41462 out of 500000 queries used.
3 Correct 34 ms 10104 KB Correct: 151839 out of 500000 queries used.
4 Correct 31 ms 9976 KB Correct: 132074 out of 500000 queries used.
5 Correct 23 ms 9208 KB Correct: 68750 out of 500000 queries used.
6 Correct 15 ms 8440 KB Correct: 23906 out of 500000 queries used.
7 Correct 15 ms 8568 KB Correct: 35451 out of 500000 queries used.
8 Correct 30 ms 9592 KB Correct: 120882 out of 500000 queries used.
9 Correct 37 ms 10104 KB Correct: 151296 out of 500000 queries used.
10 Correct 18 ms 8696 KB Correct: 42342 out of 500000 queries used.
11 Incorrect 12 ms 8440 KB Too many calls to get_distance().
12 Halted 0 ms 0 KB -