Cod sursa(job #3194982)

Utilizator Cosmin.BoeriuCosmin Boeriu George Cosmin.Boeriu Data 19 ianuarie 2024 21:08:17
Problema Taramul Nicaieri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

priority_queue<pair<int,int>> intrari, iesiri;
vector<vector<int>> graf(101);
queue<pair<int, int>>rem;
int main()
{
    int nod, grad, i, j, a, b, muchii = 0, n, vecin, nou, flag;

    fin>>n;
    for(i = 1; i <= n; i++){
        fin>>a>>b;
        iesiri.push(make_pair(a, i));
        intrari.push(make_pair(b, i));
    }

    while(!intrari.empty() && !iesiri.empty()){
        nod = iesiri.top().second;
        grad = iesiri.top().first;
        muchii += grad;
        iesiri.pop();
        flag = 0;
        for(i = 0; i < grad; i++){
            vecin = intrari.top().second;
            nou = intrari.top().first-1;
            intrari.pop();
            if(vecin == nod){
                rem.push(make_pair(nou+1, vecin));
                flag = 1;
                i--;
            }
            else{
                rem.push(make_pair(nou, vecin));
                graf[nod].push_back(intrari.top().second);
            }
        }
        for(i = 0; i < grad+flag; i++){
            if(rem.front().first > 0){
                intrari.push(rem.front());
            }
            rem.pop();
        }
    }
    fout<<muchii<<'\n';
    for(i = 1; i <= n; i++){
        for(j = 0; j < graf[i].size(); j++){
            fout<<i<<' '<<graf[i][j]<<'\n';
        }
    }



    return 0;
}