oj.uz

Submission #147015

# Submission time Handle Problem Language Result Execution time Memory
147015 2019-08-27T06:09:24 Z jun6873 City Mapping (NOI18_citymapping) C++11
57 / 100
 8 ms 1272 KB 
#include "citymapping.h"
#include <bits/stdc++.h>
using namespace std;

// long long get_distance(int X, int Y);

using lint = long long;
const lint inf = 1e18;

int n, t=0, *A, *B, *W;

void f(vector<int> v) {
    int x = v[0], y = v[0], z = v[0];
    vector<lint> a, b, c, d;

    lint mxd;

    mxd = 0;
    for (int i : v) {
        lint d = get_distance(x, i);
        if (d > mxd) mxd = d, y = i;
        a.push_back(d);
    }

    mxd = 0;
    for (int i : v) {
        lint d = get_distance(y, i);
        if (d > mxd) mxd = d, z = i;
        b.push_back(d);
    }

    for (int i : v) c.push_back(get_distance(z, i));
    for (int i=0; i<v.size(); i++) d.push_back(b[i] - c[i]);

    vector<int> ind;
    for (int i=0; i<v.size(); i++) ind.push_back(i);
    sort(ind.begin(), ind.end(), [&](int x, int y) { return (d[x] < d[y]) or (d[x] == d[y] and b[x] < b[y]); });

    vector<lint> tb, td;
    vector<int> tv;

    for (int i=0; i<b.size(); i++) tb.push_back(b[ind[i]]);
    b = tb;
    for (int i=0; i<d.size(); i++) td.push_back(d[ind[i]]);
    d = td;
    for (int i=0; i<v.size(); i++) tv.push_back(v[ind[i]]);
    v = tv;

    for (int i=0; i<v.size(); ) {
        vector<int> u;
        int k = i;
        while (i+1<v.size() and d[i] == d[i+1]) {
            u.push_back(i+1);
            i++;
        } i++;
        if (i < v.size()) {
            A[t] = v[k]; B[t] = v[i]; W[t] = b[i] - b[k]; t++;
        }
        if (!u.empty()) {
            A[t] = v[k]; B[t] = v[u[0]]; W[t] = b[u[0]] - b[k]; t++;
        }
        if (u.size() >= 2) {
            for (int &i : u) i = v[i];
            f(u);
        }
    }
}

void find_roads(int N, int Q, int a[], int b[], int w[]) {
    n = N; A = a; B = b; W = w;
    vector<int> v;
    for (int i=1; i<=n; i++) v.push_back(i);

    f(v);
}

Compilation message

citymapping.cpp: In function 'void f(std::vector<int>)':
citymapping.cpp:33:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<v.size(); i++) d.push_back(b[i] - c[i]);
                   ~^~~~~~~~~
citymapping.cpp:36:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<v.size(); i++) ind.push_back(i);
                   ~^~~~~~~~~
citymapping.cpp:42:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<b.size(); i++) tb.push_back(b[ind[i]]);
                   ~^~~~~~~~~
citymapping.cpp:44:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<d.size(); i++) td.push_back(d[ind[i]]);
                   ~^~~~~~~~~
citymapping.cpp:46:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<v.size(); i++) tv.push_back(v[ind[i]]);
                   ~^~~~~~~~~
citymapping.cpp:49:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<v.size(); ) {
                   ~^~~~~~~~~
citymapping.cpp:52:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (i+1<v.size() and d[i] == d[i+1]) {
                ~~~^~~~~~~~~
citymapping.cpp:56:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (i < v.size()) {
             ~~^~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Correct: 2997 out of 500000 queries used.
2 Correct 3 ms 504 KB Correct: 3000 out of 500000 queries used.
3 Correct 4 ms 504 KB Correct: 8529 out of 500000 queries used.
4 Correct 4 ms 504 KB Correct: 9753 out of 500000 queries used.
5 Correct 5 ms 940 KB Correct: 16638 out of 500000 queries used.

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Correct: 2997 out of 500000 queries used.
2 Correct 3 ms 504 KB Correct: 3000 out of 500000 queries used.
3 Correct 4 ms 504 KB Correct: 8529 out of 500000 queries used.
4 Correct 4 ms 504 KB Correct: 9753 out of 500000 queries used.
5 Correct 5 ms 940 KB Correct: 16638 out of 500000 queries used.
6 Correct 3 ms 632 KB Correct: 2988 out of 500000 queries used.
7 Correct 8 ms 1272 KB Correct: 29373 out of 500000 queries used.
8 Correct 4 ms 504 KB Correct: 8694 out of 500000 queries used.
9 Correct 4 ms 504 KB Correct: 10266 out of 500000 queries used.
10 Correct 4 ms 632 KB Correct: 9960 out of 500000 queries used.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Correct: 2973 out of 12000 queries used.
2 Correct 3 ms 504 KB Correct: 2979 out of 12000 queries used.
3 Correct 3 ms 504 KB Correct: 3000 out of 12000 queries used.
4 Correct 3 ms 504 KB Correct: 2979 out of 12000 queries used.
5 Correct 3 ms 504 KB Correct: 2973 out of 12000 queries used.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Correct: 2973 out of 12000 queries used.
2 Correct 3 ms 504 KB Correct: 2979 out of 12000 queries used.
3 Correct 3 ms 504 KB Correct: 3000 out of 12000 queries used.
4 Correct 3 ms 504 KB Correct: 2979 out of 12000 queries used.
5 Correct 3 ms 504 KB Correct: 2973 out of 12000 queries used.
6 Correct 3 ms 504 KB Correct: 2994 out of 12000 queries used.
7 Correct 3 ms 504 KB Correct: 2988 out of 12000 queries used.
8 Correct 3 ms 504 KB Correct: 3000 out of 12000 queries used.
9 Correct 4 ms 504 KB Correct: 2991 out of 12000 queries used.
10 Correct 3 ms 504 KB Correct: 2982 out of 12000 queries used.

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Correct: 2997 out of 500000 queries used.
2 Correct 3 ms 504 KB Correct: 3000 out of 500000 queries used.
3 Correct 4 ms 504 KB Correct: 8529 out of 500000 queries used.
4 Correct 4 ms 504 KB Correct: 9753 out of 500000 queries used.
5 Correct 5 ms 940 KB Correct: 16638 out of 500000 queries used.
6 Correct 3 ms 632 KB Correct: 2988 out of 500000 queries used.
7 Correct 8 ms 1272 KB Correct: 29373 out of 500000 queries used.
8 Correct 4 ms 504 KB Correct: 8694 out of 500000 queries used.
9 Correct 4 ms 504 KB Correct: 10266 out of 500000 queries used.
10 Correct 4 ms 632 KB Correct: 9960 out of 500000 queries used.
11 Correct 3 ms 504 KB Correct: 2973 out of 12000 queries used.
12 Correct 3 ms 504 KB Correct: 2979 out of 12000 queries used.
13 Correct 3 ms 504 KB Correct: 3000 out of 12000 queries used.
14 Correct 3 ms 504 KB Correct: 2979 out of 12000 queries used.
15 Correct 3 ms 504 KB Correct: 2973 out of 12000 queries used.
16 Correct 3 ms 504 KB Correct: 2994 out of 12000 queries used.
17 Correct 3 ms 504 KB Correct: 2988 out of 12000 queries used.
18 Correct 3 ms 504 KB Correct: 3000 out of 12000 queries used.
19 Correct 4 ms 504 KB Correct: 2991 out of 12000 queries used.
20 Correct 3 ms 504 KB Correct: 2982 out of 12000 queries used.
21 Correct 4 ms 504 KB Correct: 2988 out of 25000 queries used.
22 Correct 4 ms 632 KB Correct: 7893 out of 25000 queries used.
23 Correct 3 ms 508 KB Correct: 3099 out of 25000 queries used.
24 Correct 4 ms 632 KB Correct: 5172 out of 25000 queries used.
25 Correct 4 ms 632 KB Correct: 8739 out of 25000 queries used.
26 Correct 4 ms 504 KB Correct: 8379 out of 25000 queries used.
27 Correct 4 ms 504 KB Correct: 8517 out of 25000 queries used.
28 Correct 4 ms 632 KB Correct: 8907 out of 25000 queries used.
29 Correct 4 ms 632 KB Correct: 9282 out of 25000 queries used.
30 Correct 4 ms 632 KB Correct: 9765 out of 25000 queries used.
31 Correct 4 ms 504 KB Correct: 9801 out of 25000 queries used.
32 Correct 3 ms 632 KB Correct: 2985 out of 25000 queries used.
33 Correct 4 ms 504 KB Correct: 9750 out of 25000 queries used.
34 Correct 4 ms 552 KB Correct: 9741 out of 25000 queries used.
35 Correct 4 ms 504 KB Correct: 9792 out of 25000 queries used.
36 Correct 5 ms 508 KB Correct: 9843 out of 25000 queries used.
37 Correct 4 ms 504 KB Correct: 9696 out of 25000 queries used.
38 Correct 4 ms 504 KB Correct: 9900 out of 25000 queries used.
39 Correct 4 ms 504 KB Correct: 9741 out of 25000 queries used.
40 Correct 4 ms 504 KB Correct: 9822 out of 25000 queries used.
41 Correct 4 ms 504 KB Correct: 9765 out of 25000 queries used.
42 Correct 4 ms 508 KB Correct: 9801 out of 25000 queries used.
43 Correct 3 ms 632 KB Correct: 2994 out of 25000 queries used.
44 Correct 4 ms 504 KB Correct: 9684 out of 25000 queries used.
45 Correct 4 ms 504 KB Correct: 9672 out of 25000 queries used.
46 Correct 4 ms 504 KB Correct: 9684 out of 25000 queries used.
47 Correct 4 ms 504 KB Correct: 9786 out of 25000 queries used.
48 Correct 4 ms 504 KB Correct: 9870 out of 25000 queries used.
49 Correct 4 ms 504 KB Correct: 9810 out of 25000 queries used.
50 Correct 4 ms 504 KB Correct: 9777 out of 25000 queries used.
51 Correct 4 ms 504 KB Correct: 9798 out of 25000 queries used.
52 Correct 4 ms 504 KB Correct: 9747 out of 25000 queries used.
53 Correct 4 ms 504 KB Correct: 10245 out of 25000 queries used.
54 Incorrect 7 ms 1272 KB Too many calls to get_distance().
55 Halted 0 ms 0 KB -