oj.uz

Submission #246274

# Submission time Handle Problem Language Result Execution time Memory
246274 2020-07-08T13:56:26 Z SamAnd City Mapping (NOI18_citymapping) C++17
57 / 100
 127 ms 9196 KB 
#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++;
    }
}

int p[MAXN];
int fi(int x)
{
    if (x == p[x])
        return x;
    return p[x] = fi(p[x]);
}

void kpc(int x, int y)
{
    x = fi(x);
    y = fi(y);
    p[x] = y;
}

void solv1(int A[], int B[], int W[])
{
    vector<pair<ll, pair<int, int> > > v;
    for (int x = 1; x <= n; ++x)
    {
        for (int y = x + 1; y <= n; ++y)
        {
            v.push_back(m_p(get_distance(x, y), m_p(x, y)));
        }
    }
    sort(all(v));
    for (int x = 1; x <= n; ++x)
        p[x] = x;
    int m = 0;
    for (int i = 0; i < v.size(); ++i)
    {
        int x = v[i].se.fi;
        int y = v[i].se.se;
        if (fi(x) != fi(y))
        {
            kpc(x, y);
            A[m] = x;
            B[m] = y;
            W[m] = v[i].fi;
            m++;
        }
    }
}

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

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

Compilation message

citymapping.cpp: In function 'void solv1(int*, int*, int*)':
citymapping.cpp:128:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < v.size(); ++i)
                     ~~^~~~~~~~~~
citymapping.cpp: In function 'void solv2(int*, int*, int*)':
citymapping.cpp:43:9: warning: 'minx' may be used uninitialized in this function [-Wmaybe-uninitialized]
         if (x == minx)
         ^~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 8804 KB Correct: 498501 out of 500000 queries used.
2 Correct 121 ms 8800 KB Correct: 499500 out of 500000 queries used.
3 Correct 127 ms 8804 KB Correct: 492528 out of 500000 queries used.
4 Correct 108 ms 8804 KB Correct: 494515 out of 500000 queries used.
5 Correct 127 ms 8804 KB Correct: 498501 out of 500000 queries used.

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 8804 KB Correct: 498501 out of 500000 queries used.
2 Correct 121 ms 8800 KB Correct: 499500 out of 500000 queries used.
3 Correct 127 ms 8804 KB Correct: 492528 out of 500000 queries used.
4 Correct 108 ms 8804 KB Correct: 494515 out of 500000 queries used.
5 Correct 127 ms 8804 KB Correct: 498501 out of 500000 queries used.
6 Correct 102 ms 8940 KB Correct: 495510 out of 500000 queries used.
7 Correct 118 ms 9196 KB Correct: 497503 out of 500000 queries used.
8 Correct 97 ms 8804 KB Correct: 497503 out of 500000 queries used.
9 Correct 92 ms 8804 KB Correct: 495510 out of 500000 queries used.
10 Correct 108 ms 8812 KB Correct: 496506 out of 500000 queries used.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Correct: 1980 out of 12000 queries used.
2 Correct 5 ms 512 KB Correct: 1984 out of 12000 queries used.
3 Correct 5 ms 512 KB Correct: 1998 out of 12000 queries used.
4 Correct 6 ms 532 KB Correct: 1984 out of 12000 queries used.
5 Correct 7 ms 512 KB Correct: 1980 out of 12000 queries used.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Correct: 1980 out of 12000 queries used.
2 Correct 5 ms 512 KB Correct: 1984 out of 12000 queries used.
3 Correct 5 ms 512 KB Correct: 1998 out of 12000 queries used.
4 Correct 6 ms 532 KB Correct: 1984 out of 12000 queries used.
5 Correct 7 ms 512 KB Correct: 1980 out of 12000 queries used.
6 Correct 6 ms 512 KB Correct: 1994 out of 12000 queries used.
7 Correct 6 ms 512 KB Correct: 1990 out of 12000 queries used.
8 Correct 6 ms 512 KB Correct: 1998 out of 12000 queries used.
9 Correct 6 ms 512 KB Correct: 1992 out of 12000 queries used.
10 Correct 7 ms 512 KB Correct: 1986 out of 12000 queries used.

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 8804 KB Correct: 498501 out of 500000 queries used.
2 Correct 121 ms 8800 KB Correct: 499500 out of 500000 queries used.
3 Correct 127 ms 8804 KB Correct: 492528 out of 500000 queries used.
4 Correct 108 ms 8804 KB Correct: 494515 out of 500000 queries used.
5 Correct 127 ms 8804 KB Correct: 498501 out of 500000 queries used.
6 Correct 102 ms 8940 KB Correct: 495510 out of 500000 queries used.
7 Correct 118 ms 9196 KB Correct: 497503 out of 500000 queries used.
8 Correct 97 ms 8804 KB Correct: 497503 out of 500000 queries used.
9 Correct 92 ms 8804 KB Correct: 495510 out of 500000 queries used.
10 Correct 108 ms 8812 KB Correct: 496506 out of 500000 queries used.
11 Correct 5 ms 512 KB Correct: 1980 out of 12000 queries used.
12 Correct 5 ms 512 KB Correct: 1984 out of 12000 queries used.
13 Correct 5 ms 512 KB Correct: 1998 out of 12000 queries used.
14 Correct 6 ms 532 KB Correct: 1984 out of 12000 queries used.
15 Correct 7 ms 512 KB Correct: 1980 out of 12000 queries used.
16 Correct 6 ms 512 KB Correct: 1994 out of 12000 queries used.
17 Correct 6 ms 512 KB Correct: 1990 out of 12000 queries used.
18 Correct 6 ms 512 KB Correct: 1998 out of 12000 queries used.
19 Correct 6 ms 512 KB Correct: 1992 out of 12000 queries used.
20 Correct 7 ms 512 KB Correct: 1986 out of 12000 queries used.
21 Incorrect 5 ms 512 KB Reported list of edges differ from actual.
22 Halted 0 ms 0 KB -