Submission #588149

#	Time	Username	Problem	Language	Result	Execution time	Memory
588149		Jomnoi	Road Closures (APIO21_roads)	C++17	5 / 100	47 ms	5684 KiB

roads

#include <bits/stdc++.h>
#include "roads.h"
using namespace std;

const int MAX_N = 1e5 + 5;

int id[MAX_N];
bool used[MAX_N];

vector <long long> minimum_closure_costs(int N, vector <int> U, vector <int> V, vector <int> W) {
    bool subtask1 = true, subtask2 = true;

    for(int i = 0; i < N - 1; i++) {
        if(U[i] != 0 and V[i] != 0) {
            subtask1 = false;
        }
        if(U[i] != i or V[i] != i + 1) {
            subtask2 = false;
        }
    }
    
    vector <long long> ans;
    if(subtask1 == true) {
        sort(W.rbegin(), W.rend());

        long long sum = 0;
        for(int i = 0; i < N - 1; i++) {
            sum += W[i];
        }
        for(int i = 0; i < N - 1; i++) {
            ans.push_back(sum);
            sum -= W[i];
        }
        ans.push_back(0);
    }
    else if(subtask2 == true) {
        iota(id, id + N - 1, 0);
        sort(id, id + N - 1, [&](const int &a, const int &b) {
            return W[a] > W[b];
        });

        long long sum = 0;
        for(int i = 0; i < N - 1; i++) {
            sum += W[id[i]];
        }
        ans.push_back(sum);

        for(int i = 0; i < N - 1; i++) {
            if(used[U[id[i]]] == false and used[V[id[i]]] == false) {
                sum -= W[id[i]];
                used[U[id[i]]] = true;
                used[V[id[i]]] = true;
            }
        }
        ans.push_back(sum);

        for(int i = 0; i < N - 2; i++) {
            ans.push_back(0);
        }
    }
    else if(N <= 200) {
        // do something
    }
    else if(N <= 2000) {
        // do something
    }
    return ans;
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 14
• Subtask 4: 0 / 10
• Subtask 5: 0 / 17
• Subtask 6: 0 / 25
• Subtask 7: 0 / 22