oj.uz

Submission #246227

# Submission time Handle Problem Language Result Execution time Memory
246227 2020-07-08T11:50:41 Z SamAnd City Mapping (NOI18_citymapping) C++17
32 / 100
 6 ms 512 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++;
    }
}

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

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

Compilation message

citymapping.cpp: In function 'void solv2(int*, int*, int*)':
citymapping.cpp:44:9: warning: 'minx' may be used uninitialized in this function [-Wmaybe-uninitialized]
         if (x == minx)
         ^~

Subtask #1
0 / 9.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 #2
0 / 16.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 #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 512 KB Correct: 1980 out of 12000 queries used.
2 Correct 6 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 5 ms 512 KB Correct: 1984 out of 12000 queries used.
5 Correct 6 ms 512 KB Correct: 1980 out of 12000 queries used.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 512 KB Correct: 1980 out of 12000 queries used.
2 Correct 6 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 5 ms 512 KB Correct: 1984 out of 12000 queries used.
5 Correct 6 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 6 ms 512 KB Correct: 1986 out of 12000 queries used.

Subtask #5
0 / 43.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 -