Cod sursa(job #1840417)

Utilizator Mihai_PredaPreda Mihai Dragos Mihai_Preda Data 4 ianuarie 2017 13:52:45
Problema Balanta Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.65 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream in("balanta.in");
ofstream out("balanta.out");

struct cantarire
{
    int k;
    vector<int> st;
    vector<int> dr;
    int r;
};

const int nMax = 1030;
const int mMax = 1030;

int n, m;
cantarire op[mMax];

int falsa[nMax];
// 0 = sigur nu e falsa
// 1 = poate fi falsa
// 2 = nu stim

int raspGrea, raspUsoara;
bool grea, usoara;

void citire()
{
    in >> n >> m;
    for(int i = 1; i <= m; ++i)
    {
        in >> op[i].k;
        op[i].st.resize(op[i].k + 1);
        op[i].dr.resize(op[i].k + 1);
        for(int j = 1; j <= op[i].k; ++j)
            in >> op[i].st[j];
        for(int j = 1; j <= op[i].k; ++j)
            in >> op[i].dr[j];
        in >> op[i].r;
    }
}

void rezGrea()
{
    //presupunem ca moneda este mai grea

    for(int i = 1; i <= n; ++i)
        falsa[i] = 2;

    for(int i = 1; i <= m; ++i)
    {
        if(op[i].r == 0)
        {
            for(int j = 1; j <= op[i].k; ++j)
            {
                falsa[op[i].st[j]] = 0;
                falsa[op[i].dr[j]] = 0;
            }
        }
        else if(op[i].r == 1)
        {
            for(int j = 1; j <= op[i].k; ++j)
            {
                if(falsa[op[i].st[j]] == 2)
                    falsa[op[i].st[j]] = 1;
            }
            for(int j = 1; j <= op[i].k; ++j)
                falsa[op[i].dr[j]] = 0;
        }
        else
        {
            for(int j = 1; j <= op[i].k; ++j)
            {
                if(falsa[op[i].dr[j]] == 2)
                    falsa[op[i].dr[j]] = 1;
            }

            for(int j = 1; j <= op[i].k; ++j)
                falsa[op[i].st[j]] = 0;
        }
    }
}

void rezUsoara()
{
    //presupunem ca moneda este mai usoara

    for(int i = 1; i <= n; ++i)
        falsa[i] = 2;

    for(int i = 1; i <= m; ++i)
    {
        if(op[i].r == 0)
        {
            for(int j = 1; j <= op[i].k; ++j)
            {
                falsa[op[i].st[j]] = 0;
                falsa[op[i].dr[j]] = 0;
            }
        }
        else if(op[i].r == 2)
        {
            for(int j = 1; j <= op[i].k; ++j)
            {
                if(falsa[op[i].st[j]] == 2)
                    falsa[op[i].st[j]] = 1;
            }
            for(int j = 1; j <= op[i].k; ++j)
                falsa[op[i].dr[j]] = 0;
        }
        else
        {
            for(int j = 1; j <= op[i].k; ++j)
            {
                if(falsa[op[i].dr[j]] == 2)
                    falsa[op[i].dr[j]] = 1;
            }

            for(int j = 1; j <= op[i].k; ++j)
                falsa[op[i].st[j]] = 0;
        }
    }
}

void rezolvare()
{
    rezGrea();
    for(int i = 1; i <= n; ++i)
    {
        if(falsa[i] == 1)
        {
            if(raspGrea == 0)
            {
                raspGrea = i;
                grea = true;
            }
            else
            {
                grea = false;
                break;
            }
        }
    }

    rezUsoara();
    for(int i = 1; i <= n; ++i)
    {
        if(falsa[i] == 1)
        {
            if(raspUsoara == 0)
            {
                raspUsoara = i;
                usoara = true;
            }
            else
            {
                usoara = false;
                break;
            }
        }
    }
    if(grea == true && usoara == false)
        out << raspGrea;
    else if(grea == false && usoara == true)
        out << raspUsoara;
    else
        out << 0;
}

int main()
{
    citire();
    rezolvare();
    return 0;
}