Cod sursa(job #2951230)

Utilizator VictorB11Badulescu Victor VictorB11 Data 5 decembrie 2022 18:57:40
Problema Taramul Nicaieri Scor 5
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.83 kb
#include <bits/stdc++.h>
using namespace std;
//infoarena taramul nicaieri
int main() {
    ifstream fin("harta.in");
    ofstream fout("harta.out");
    int n;
    fin>>n;
    vector<pair<int, int>> grade;
    grade.emplace_back(0, 0);
    int x, y;
    for(int i = 1; i <= n; i++)
    {
        fin>>x>>y;
        grade.emplace_back(x, y);
    }
    vector<vector<int>> drumuri(n + 1);
    vector<int> drumuriUltimNod(n+1);
    int nrDrumuri = 0;
    for(int i = 1; i <= n; i++){
        if(grade[i].first) {
            for (int j = 1; j <= n; j++) {
                if (i != j && grade[j].second) {
                    grade[i].first--;
                    grade[j].second--;
                    drumuri[i].push_back(j);
                    nrDrumuri++;
                    if(i == n)
                        drumuriUltimNod[j] = 1;
                    if (grade[i].first == 0) break;
                }
            }
        }
    }
    if(grade[n].first){
        for(int i = n-1; i >= 1; i--){
            if(drumuri[i][drumuri[i].size()-1] != n){
                for(int j = 0; j < drumuri[i].size(); j++){
                    int nod = drumuri[i][j];
                    if(!drumuriUltimNod[nod])
                    {
                        drumuri[n].push_back(nod);
                        drumuriUltimNod[nod] = 1;

                        drumuri[i].erase(drumuri[i].begin() + j);
                        drumuri[i].push_back(n);

                        grade[n].first--;
                        grade[n].second--;
                        nrDrumuri++;
                    }
                    if(!grade[n].first) break;
                }
            }
            if(!grade[n].first) break;
        }
    }
    fout<<nrDrumuri<<'\n';
    for(int i = 1; i <= n; i++)
        for(auto nod : drumuri[i])
            fout<<i<<' '<<nod<<'\n';

    return 0;
}