oj.uz

Submission #246273

# Submission time Handle Problem Language Result Execution time Memory
246273 2020-07-08T13:55:31 Z SamAnd City Mapping (NOI18_citymapping) C++17
25 / 100
 126 ms 8932 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));
    sort(all(r));

    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 125 ms 8800 KB Correct: 498501 out of 500000 queries used.
2 Correct 125 ms 8812 KB Correct: 499500 out of 500000 queries used.
3 Correct 120 ms 8812 KB Correct: 492528 out of 500000 queries used.
4 Correct 106 ms 8812 KB Correct: 494515 out of 500000 queries used.
5 Correct 126 ms 8804 KB Correct: 498501 out of 500000 queries used.

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 8800 KB Correct: 498501 out of 500000 queries used.
2 Correct 125 ms 8812 KB Correct: 499500 out of 500000 queries used.
3 Correct 120 ms 8812 KB Correct: 492528 out of 500000 queries used.
4 Correct 106 ms 8812 KB Correct: 494515 out of 500000 queries used.
5 Correct 126 ms 8804 KB Correct: 498501 out of 500000 queries used.
6 Correct 98 ms 8932 KB Correct: 495510 out of 500000 queries used.
7 Correct 109 ms 8932 KB Correct: 497503 out of 500000 queries used.
8 Correct 97 ms 8804 KB Correct: 497503 out of 500000 queries used.
9 Correct 95 ms 8888 KB Correct: 495510 out of 500000 queries used.
10 Correct 110 ms 8800 KB Correct: 496506 out of 500000 queries used.

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 512 KB Reported list of edges differ from actual.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 512 KB Reported list of edges differ from actual.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 8800 KB Correct: 498501 out of 500000 queries used.
2 Correct 125 ms 8812 KB Correct: 499500 out of 500000 queries used.
3 Correct 120 ms 8812 KB Correct: 492528 out of 500000 queries used.
4 Correct 106 ms 8812 KB Correct: 494515 out of 500000 queries used.
5 Correct 126 ms 8804 KB Correct: 498501 out of 500000 queries used.
6 Correct 98 ms 8932 KB Correct: 495510 out of 500000 queries used.
7 Correct 109 ms 8932 KB Correct: 497503 out of 500000 queries used.
8 Correct 97 ms 8804 KB Correct: 497503 out of 500000 queries used.
9 Correct 95 ms 8888 KB Correct: 495510 out of 500000 queries used.
10 Correct 110 ms 8800 KB Correct: 496506 out of 500000 queries used.
11 Incorrect 5 ms 512 KB Reported list of edges differ from actual.
12 Halted 0 ms 0 KB -