oj.uz

Submission #499287

# Submission time Handle Problem Language Result Execution time Memory
499287 2021-12-27T19:04:25 Z blue City Mapping (NOI18_citymapping) C++17
25 / 100
 85 ms 8812 KB 
#include "citymapping.h"
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

using ll = long long;
using vi = vector<int>;

struct edge
{
    ll w;
    int u;
    int v;
};

bool operator < (edge A, edge B)
{
    return A.w < B.w;
}

void find_roads(int N, int Q, int A[], int B[], int W[])
{
	vector<edge> E;
    for(int i = 1; i <= N; i++)
        for(int j = i+1; j <= N; j++)
            E.push_back(edge{get_distance(i, j), i, j});

    sort(E.begin(), E.end());

    int ct = -1;

    vi cc(N+1);
    for(int i = 1; i <= N; i++) cc[i] = i;

    // for(auto e: E) cerr << get<1>(e) << ' ' << get<2>(e) << ' ' << get<0>(e) << '\n';

    for(auto e: E)
    {
        ll w = e.w;
        int u = e.u;
        int v = e.v;
        if(cc[u] == cc[v]) continue;

        int ccu = cc[u];

        for(int i = 1; i <= N; i++)
            if(cc[i] == ccu)
                cc[i] = cc[v];

        ct++;
        A[ct] = u;
        B[ct] = v;
        W[ct] = w;
    }
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 8756 KB Correct: 498501 out of 500000 queries used.
2 Correct 71 ms 8728 KB Correct: 499500 out of 500000 queries used.
3 Correct 61 ms 8768 KB Correct: 492528 out of 500000 queries used.
4 Correct 51 ms 8764 KB Correct: 494515 out of 500000 queries used.
5 Correct 68 ms 8696 KB Correct: 498501 out of 500000 queries used.

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 8756 KB Correct: 498501 out of 500000 queries used.
2 Correct 71 ms 8728 KB Correct: 499500 out of 500000 queries used.
3 Correct 61 ms 8768 KB Correct: 492528 out of 500000 queries used.
4 Correct 51 ms 8764 KB Correct: 494515 out of 500000 queries used.
5 Correct 68 ms 8696 KB Correct: 498501 out of 500000 queries used.
6 Correct 77 ms 8800 KB Correct: 495510 out of 500000 queries used.
7 Correct 81 ms 8752 KB Correct: 497503 out of 500000 queries used.
8 Correct 78 ms 8776 KB Correct: 497503 out of 500000 queries used.
9 Correct 75 ms 8812 KB Correct: 495510 out of 500000 queries used.
10 Correct 85 ms 8764 KB Correct: 496506 out of 500000 queries used.

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 844 KB Too many calls to get_distance().
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 844 KB Too many calls to get_distance().
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 8756 KB Correct: 498501 out of 500000 queries used.
2 Correct 71 ms 8728 KB Correct: 499500 out of 500000 queries used.
3 Correct 61 ms 8768 KB Correct: 492528 out of 500000 queries used.
4 Correct 51 ms 8764 KB Correct: 494515 out of 500000 queries used.
5 Correct 68 ms 8696 KB Correct: 498501 out of 500000 queries used.
6 Correct 77 ms 8800 KB Correct: 495510 out of 500000 queries used.
7 Correct 81 ms 8752 KB Correct: 497503 out of 500000 queries used.
8 Correct 78 ms 8776 KB Correct: 497503 out of 500000 queries used.
9 Correct 75 ms 8812 KB Correct: 495510 out of 500000 queries used.
10 Correct 85 ms 8764 KB Correct: 496506 out of 500000 queries used.
11 Incorrect 2 ms 844 KB Too many calls to get_distance().
12 Halted 0 ms 0 KB -