oj.uz

Submission #520856

# Submission time Handle Problem Language Result Execution time Memory
520856 2022-01-31T08:00:01 Z danikoynov Road Construction (JOI21_road_construction) C++14
11 / 100
 255 ms 14432 KB 
/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
const int maxn = 3e5 + 10;

int n, k;
ll x[maxn], y[maxn], bef[maxn], nxt[maxn];

struct element
{
    int idx;
    ll sum;

    bool operator < (const element &e) const
    {
        return sum > e.sum;
    }
};
void solve()
{
    cin >> n >> k;
    bool y0 = true;
    for (int i = 1; i <= n; i ++)
    {
        cin >> x[i] >> y[i];
        if (y[i] != 0)
            y0 = false;
    }

    if (n <= 1000)
    {
        vector < ll > v;
        for (int i = 1; i <= n; i ++)
            for (int j = i + 1; j <= n; j ++)
            {
                v.push_back(abs(x[i] - x[j]) + abs(y[i] - y[j]));
            }

        sort(v.begin(), v.end());
        for (int i = 0; i < k; i ++)
            cout << v[i] << endl;
    }
    else
    if (y0 == true)
    {
        sort(x + 1, x + n + 1);
        priority_queue < element > pq;
        for (int i = 1; i <= n; i ++)
        {
            bef[i] = i - 1;
            if (i != 1)
            {
                element e;
                e.sum = x[i] - x[i - 1];
                e.idx = i;
                pq.push(e);
            }
        }

        for (int q = 0; q < k; q ++)
        {
            element e = pq.top();
            pq.pop();
            cout << e.sum << endl;
            bef[e.idx] --;
            if (bef[e.idx] != 0)
            {
                e.sum = x[e.idx] - x[bef[e.idx]];
                pq.push(e);
            }
        }
    }

}

int main()
{
    solve();
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 6828 KB Output is correct
2 Correct 63 ms 6852 KB Output is correct
3 Correct 40 ms 5040 KB Output is correct
4 Correct 41 ms 4964 KB Output is correct
5 Correct 60 ms 5808 KB Output is correct
6 Correct 21 ms 4540 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 14248 KB Output is correct
2 Correct 245 ms 14424 KB Output is correct
3 Correct 41 ms 4852 KB Output is correct
4 Correct 198 ms 14188 KB Output is correct
5 Correct 222 ms 14396 KB Output is correct
6 Correct 197 ms 14432 KB Output is correct
7 Correct 196 ms 13780 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 209 ms 9028 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 209 ms 9028 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 6828 KB Output is correct
2 Correct 63 ms 6852 KB Output is correct
3 Correct 40 ms 5040 KB Output is correct
4 Correct 41 ms 4964 KB Output is correct
5 Correct 60 ms 5808 KB Output is correct
6 Correct 21 ms 4540 KB Output is correct
7 Incorrect 74 ms 3716 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 6828 KB Output is correct
2 Correct 63 ms 6852 KB Output is correct
3 Correct 40 ms 5040 KB Output is correct
4 Correct 41 ms 4964 KB Output is correct
5 Correct 60 ms 5808 KB Output is correct
6 Correct 21 ms 4540 KB Output is correct
7 Correct 255 ms 14248 KB Output is correct
8 Correct 245 ms 14424 KB Output is correct
9 Correct 41 ms 4852 KB Output is correct
10 Correct 198 ms 14188 KB Output is correct
11 Correct 222 ms 14396 KB Output is correct
12 Correct 197 ms 14432 KB Output is correct
13 Correct 196 ms 13780 KB Output is correct
14 Incorrect 209 ms 9028 KB Output isn't correct
15 Halted 0 ms 0 KB -