Cod sursa(job #3190339)

Utilizator ZiGabiZiTilica Gabriel Lucian ZiGabiZi Data 7 ianuarie 2024 15:31:22
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <vector>
#include <fstream>
#include <algorithm>
using namespace std;

int main() {
    ifstream f("harta.in");
    ofstream g("harta.out");
    int n;
    f >> n;
    vector<int> out_degree(n + 1), in_degree(n + 1);
    int total_roads = 0;

    for (int i = 1; i <= n; ++i) {
        f >> out_degree[i] >> in_degree[i];
        total_roads += out_degree[i];
    }
    g << total_roads << "\n";

    for (int i = 1; i <= n; ++i) {
        vector<pair<int, int>> destinations;
        for (int j = 1; j <= n; ++j) {
            if (j != i) {
                destinations.emplace_back(in_degree[j], j);
            }
        }
        sort(destinations.rbegin(), destinations.rend()); // Sortez in ordine descrescatoare dupa in-degree

        for (int j = 0; j < out_degree[i]; ++j) {
            g << i << " ";
            int next_city = 0;
            for (const auto& dest : destinations) {
                if (dest.first > 0) {
                    next_city = dest.second;
                    --in_degree[next_city];
                    destinations.erase(find(destinations.begin(), destinations.end(), dest));
                    break;
                }
            }
            g << next_city << "\n";
        }
    }
    return 0;
}