Cod sursa(job #3190337)

Utilizator ZiGabiZiTilica Gabriel Lucian ZiGabiZi Data 7 ianuarie 2024 15:27:50
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <bits/stdc++.h>
using namespace std;

int main() {
    ifstream fin("harta.in");
    ofstream fout("harta.out");

    int n;
    fin >> n;

    vector<int> out_degree(n + 1), in_degree(n + 1);
    int total_roads = 0;

    for (int i = 1; i <= n; ++i) {
        fin >> out_degree[i] >> in_degree[i];
        total_roads += out_degree[i];
    }

    fout << 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.push_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) {
            fout << 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;
                }
            }

            fout << next_city << "\n";
        }
    }

    fin.close();
    fout.close();
    return 0;
}