Enunț

Cu ocazia sărbătoririi marii victorii de la ONI2017, cei 10 Bistrițeni au pornit la drum cu scopul de a-și întemeia o țară. După multe dezbateri, aceștia s-au hotărât să o numească Zoomba. Și au mers ei ce au mers, până au ajuns într-un ținut pustiu, iar atunci, marele Zoli a spus: “Și aici să fie întemeiată Zoomba!” (La început, Zoomba nu are niciun oraș). Iulia are sarcina de a construi orașele, iar Maria va construi drumurile ce vor conecta orașele. Astfel, se disting următoarele evenimente:

1: Iulia construiește un nou oraș. Dacă ultimul oraș construit este orașul x, atunci noul oraș va fi x + 1 (Dacă nu există niciun oraș în acel moment, atunci noul oraș construit va fi 1).
2 x y c: Maria propune construcția unui drum bidirecțional ce leagă orașul x de orașul y de cost c.
3 x: Zoli se întreabă care este costul minim pentru a lega un număr maxim de orașe (folosind drumurile propuse de Maria) cu scopul construirii unui județ (un județ este o grupare de orașe în care se poate ajunge din orice oraș în orice alt oraș) ce conține orașul x.

Cerința

Scrieți un program care procesează M evenimente de tipurile precizate mai sus, și afișează în fișierul de ieșire rezultatele evenimentelor de tipul 3.

Date de intrare

Fișierul de intrare episodul1.in conține pe prima linie numărul M, iar pe fiecare linie din cele M, se va afla câte un eveniment, cu formatul specificat mai sus.

Date de ieșire

Fișierul de ieșire episodul1.out va conține pe fiecare linie câte un număr, reprezentând răspunsurile operațiilor de tip 3, în ordiea în care acestea apar în fișierul de intrare.

Restricții și precizări

1 ≤ M ≤ 1.000.000
Pentru orice operație de tip 2, C este maxim până în punctul respectiv.
Costul unui drum nu depășește 100.000.000
InParser
OutParser

Exemplu

episodul1.in

episodul1.out

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema episodul1:

//Popa Bogdan Ioan, clasa a X-a, Colegiul National Aurel Vlaicu Orastie
#include <bits/stdc++.h>

#define ll long long
#define Nmax 1000005

using namespace std;

class InParser {
private:
    FILE *fin;
    char *buff;
    int sp;

    char read_ch() {
        ++sp;
        if (sp == 4096) {
            sp = 0;
            fread(buff, 1, 4096, fin);
        }
        return buff[sp];
    }

public:
    InParser(const char* nume) {
        fin = fopen(nume, "r");
        buff = new char[4096]();
        sp = 4095;
    }

    InParser& operator >> (int &n) {
        char c;
        while (!isdigit(c = read_ch()) && c != '-');
        int sgn = 1;
        if (c == '-') {
            n = 0;
            sgn = -1;
        } else {
            n = c - '0';
        }
        while (isdigit(c = read_ch())) {
            n = 10 * n + c - '0';
        }
        n *= sgn;
        return *this;
    }

    InParser& operator >> (long long &n) {
        char c;
        n = 0;
        while (!isdigit(c = read_ch()) && c != '-');
        long long sgn = 1;
        if (c == '-') {
            n = 0;
            sgn = -1;
        } else {
            n = c - '0';
        }
        while (isdigit(c = read_ch())) {
            n = 10 * n + c - '0';
        }
        n *= sgn;
        return *this;
    }
};

class OutParser {
private:
    FILE *fout;
    char *buff;
    int sp;

    void write_ch(char ch) {
        if (sp == 50000) {
            fwrite(buff, 1, 50000, fout);
            sp = 0;
            buff[sp++] = ch;
        } else {
            buff[sp++] = ch;
        }
    }


public:
    OutParser(const char* name) {
        fout = fopen(name, "w");
        buff = new char[50000]();
        sp = 0;
    }
    ~OutParser() {
        fwrite(buff, 1, sp, fout);
        fclose(fout);
    }

    OutParser& operator << (int vu32) {
        if (vu32 <= 9) {
            write_ch(vu32 + '0');
        } else {
            (*this) << (vu32 / 10);
            write_ch(vu32 % 10 + '0');
        }
        return *this;
    }

    OutParser& operator << (long long vu64) {
        if (vu64 <= 9) {
            write_ch(vu64 + '0');
        } else {
            (*this) << (vu64 / 10);
            write_ch(vu64 % 10 + '0');
        }
        return *this;
    }

    OutParser& operator << (char ch) {
        write_ch(ch);
        return *this;
    }
    OutParser& operator << (const char *ch) {
        while (*ch) {
            write_ch(*ch);
            ++ch;
        }
        return *this;
    }
};

InParser fin("episodul1.in");
OutParser fout("episodul1.out");

int M, N;
int t;
int T[Nmax];
int L[Nmax];
ll APM[Nmax];

int find(int node)
{
    if(node != T[node])
        T[node] = find(T[node]);
    return T[node];
}

void unite(int a, int b, int cost)
{
    if(L[a] < L[b])
        swap(a, b);
    T[b] = a;
    if(L[a] == L[b])
        L[a]++;
    APM[a] += APM[b] + cost;
}

void insertEdge(int x, int y, int c)
{
    int tx = find(x);
    int ty = find(y);
    if(tx != ty)
        unite(tx, ty, c);
}

int main()
{
    for(fin >> M; M; M--)
    {
        int t;
        fin >> t;
        if(t == 1)
        {
            ++N;
            T[N] = N;
            L[N] = 1;
            APM[N] = 0;
        }
        if(t == 2)
        {
            int x, y, c;
            fin >> x >> y >> c;
            insertEdge(x, y, c);
        }
        if(t == 3)
        {
            int x;
            fin >> x;
            fout << APM[find(x)] << "\n";
        }
    }
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #2042 episodul1

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2042 episodul1 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #2042 episodul1