oj.uz

Submission #147024

# Submission time Handle Problem Language Result Execution time Memory
147024 2019-08-27T07:14:37 Z jun6873 City Mapping (NOI18_citymapping) C++11
57 / 100
 7 ms 1528 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 y = v[v.size()-1], z = v[0];
    vector<lint> a, b, c, d;

    lint mxd;

    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);

    lint mx = 0;
    int k;
    for (int i=2; i<=n; i++) {
        lint now = get_distance(1, i);
        if (now > mx) {
            mx = now;
            k = i;
        }
    }
    swap(v[k-1], v[n-1]);

    f(v);
}

Compilation message

citymapping.cpp: In function 'void f(std::vector<int>)':
citymapping.cpp:26: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:29: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:35: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:37: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:39: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:42:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<v.size(); ) {
                   ~^~~~~~~~~
citymapping.cpp:45:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (i+1<v.size() and d[i] == d[i+1]) {
                ~~~^~~~~~~~~
citymapping.cpp:49:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (i < v.size()) {
             ~~^~~~~~~~~~
citymapping.cpp: In function 'void find_roads(int, int, int*, int*, int*)':
citymapping.cpp:76:13: warning: 'k' may be used uninitialized in this function [-Wmaybe-uninitialized]
     swap(v[k-1], v[n-1]);
            ~^~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 632 KB Correct: 2996 out of 500000 queries used.
2 Correct 3 ms 504 KB Correct: 2999 out of 500000 queries used.
3 Correct 4 ms 504 KB Correct: 6686 out of 500000 queries used.
4 Correct 4 ms 504 KB Correct: 7496 out of 500000 queries used.
5 Correct 5 ms 912 KB Correct: 12090 out of 500000 queries used.

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 632 KB Correct: 2996 out of 500000 queries used.
2 Correct 3 ms 504 KB Correct: 2999 out of 500000 queries used.
3 Correct 4 ms 504 KB Correct: 6686 out of 500000 queries used.
4 Correct 4 ms 504 KB Correct: 7496 out of 500000 queries used.
5 Correct 5 ms 912 KB Correct: 12090 out of 500000 queries used.
6 Correct 3 ms 632 KB Correct: 2987 out of 500000 queries used.
7 Correct 6 ms 1144 KB Correct: 20579 out of 500000 queries used.
8 Correct 4 ms 504 KB Correct: 6793 out of 500000 queries used.
9 Correct 5 ms 632 KB Correct: 7839 out of 500000 queries used.
10 Correct 4 ms 632 KB Correct: 7636 out of 500000 queries used.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Correct: 2972 out of 12000 queries used.
2 Correct 3 ms 504 KB Correct: 2978 out of 12000 queries used.
3 Correct 3 ms 504 KB Correct: 2999 out of 12000 queries used.
4 Correct 4 ms 504 KB Correct: 2978 out of 12000 queries used.
5 Correct 3 ms 504 KB Correct: 2972 out of 12000 queries used.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Correct: 2972 out of 12000 queries used.
2 Correct 3 ms 504 KB Correct: 2978 out of 12000 queries used.
3 Correct 3 ms 504 KB Correct: 2999 out of 12000 queries used.
4 Correct 4 ms 504 KB Correct: 2978 out of 12000 queries used.
5 Correct 3 ms 504 KB Correct: 2972 out of 12000 queries used.
6 Correct 3 ms 532 KB Correct: 2993 out of 12000 queries used.
7 Correct 4 ms 504 KB Correct: 2987 out of 12000 queries used.
8 Correct 4 ms 632 KB Correct: 2999 out of 12000 queries used.
9 Correct 3 ms 632 KB Correct: 2990 out of 12000 queries used.
10 Correct 3 ms 504 KB Correct: 2981 out of 12000 queries used.

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 632 KB Correct: 2996 out of 500000 queries used.
2 Correct 3 ms 504 KB Correct: 2999 out of 500000 queries used.
3 Correct 4 ms 504 KB Correct: 6686 out of 500000 queries used.
4 Correct 4 ms 504 KB Correct: 7496 out of 500000 queries used.
5 Correct 5 ms 912 KB Correct: 12090 out of 500000 queries used.
6 Correct 3 ms 632 KB Correct: 2987 out of 500000 queries used.
7 Correct 6 ms 1144 KB Correct: 20579 out of 500000 queries used.
8 Correct 4 ms 504 KB Correct: 6793 out of 500000 queries used.
9 Correct 5 ms 632 KB Correct: 7839 out of 500000 queries used.
10 Correct 4 ms 632 KB Correct: 7636 out of 500000 queries used.
11 Correct 3 ms 504 KB Correct: 2972 out of 12000 queries used.
12 Correct 3 ms 504 KB Correct: 2978 out of 12000 queries used.
13 Correct 3 ms 504 KB Correct: 2999 out of 12000 queries used.
14 Correct 4 ms 504 KB Correct: 2978 out of 12000 queries used.
15 Correct 3 ms 504 KB Correct: 2972 out of 12000 queries used.
16 Correct 3 ms 532 KB Correct: 2993 out of 12000 queries used.
17 Correct 4 ms 504 KB Correct: 2987 out of 12000 queries used.
18 Correct 4 ms 632 KB Correct: 2999 out of 12000 queries used.
19 Correct 3 ms 632 KB Correct: 2990 out of 12000 queries used.
20 Correct 3 ms 504 KB Correct: 2981 out of 12000 queries used.
21 Correct 3 ms 504 KB Correct: 2987 out of 25000 queries used.
22 Correct 4 ms 632 KB Correct: 6260 out of 25000 queries used.
23 Correct 3 ms 504 KB Correct: 3058 out of 25000 queries used.
24 Correct 4 ms 632 KB Correct: 4439 out of 25000 queries used.
25 Correct 4 ms 632 KB Correct: 6823 out of 25000 queries used.
26 Correct 4 ms 556 KB Correct: 6576 out of 25000 queries used.
27 Correct 4 ms 504 KB Correct: 6671 out of 25000 queries used.
28 Correct 2 ms 504 KB Correct: 6933 out of 25000 queries used.
29 Correct 4 ms 504 KB Correct: 7187 out of 25000 queries used.
30 Correct 4 ms 632 KB Correct: 7501 out of 25000 queries used.
31 Correct 4 ms 632 KB Correct: 7532 out of 25000 queries used.
32 Correct 3 ms 504 KB Correct: 2984 out of 25000 queries used.
33 Correct 4 ms 632 KB Correct: 7493 out of 25000 queries used.
34 Correct 4 ms 504 KB Correct: 7492 out of 25000 queries used.
35 Correct 5 ms 508 KB Correct: 7523 out of 25000 queries used.
36 Correct 5 ms 504 KB Correct: 7553 out of 25000 queries used.
37 Correct 4 ms 504 KB Correct: 7457 out of 25000 queries used.
38 Correct 4 ms 504 KB Correct: 7594 out of 25000 queries used.
39 Correct 4 ms 504 KB Correct: 7492 out of 25000 queries used.
40 Correct 4 ms 504 KB Correct: 7546 out of 25000 queries used.
41 Correct 4 ms 504 KB Correct: 7508 out of 25000 queries used.
42 Correct 4 ms 504 KB Correct: 7530 out of 25000 queries used.
43 Correct 3 ms 632 KB Correct: 2993 out of 25000 queries used.
44 Correct 5 ms 504 KB Correct: 7446 out of 25000 queries used.
45 Correct 4 ms 504 KB Correct: 7438 out of 25000 queries used.
46 Correct 4 ms 504 KB Correct: 7446 out of 25000 queries used.
47 Correct 5 ms 632 KB Correct: 7522 out of 25000 queries used.
48 Correct 4 ms 504 KB Correct: 7575 out of 25000 queries used.
49 Correct 5 ms 504 KB Correct: 7534 out of 25000 queries used.
50 Correct 4 ms 632 KB Correct: 7515 out of 25000 queries used.
51 Correct 4 ms 504 KB Correct: 7527 out of 25000 queries used.
52 Correct 4 ms 632 KB Correct: 7496 out of 25000 queries used.
53 Correct 4 ms 632 KB Correct: 7829 out of 25000 queries used.
54 Correct 7 ms 1272 KB Correct: 22177 out of 25000 queries used.
55 Correct 4 ms 504 KB Correct: 7518 out of 25000 queries used.
56 Correct 4 ms 632 KB Correct: 7588 out of 25000 queries used.
57 Correct 4 ms 632 KB Correct: 7878 out of 25000 queries used.
58 Correct 4 ms 504 KB Correct: 7439 out of 25000 queries used.
59 Correct 4 ms 504 KB Correct: 7435 out of 25000 queries used.
60 Correct 5 ms 636 KB Correct: 8859 out of 25000 queries used.
61 Correct 4 ms 632 KB Correct: 8353 out of 25000 queries used.
62 Correct 4 ms 632 KB Correct: 7777 out of 25000 queries used.
63 Correct 4 ms 632 KB Correct: 8393 out of 25000 queries used.
64 Correct 4 ms 632 KB Correct: 7969 out of 25000 queries used.
65 Correct 5 ms 892 KB Correct: 10308 out of 25000 queries used.
66 Correct 4 ms 632 KB Correct: 7850 out of 25000 queries used.
67 Correct 4 ms 504 KB Correct: 3374 out of 25000 queries used.
68 Incorrect 7 ms 1528 KB Too many calls to get_distance().
69 Halted 0 ms 0 KB -