제출 #1290352

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290352		SSKMF	Restore Array (RMI19_restore)	C++20	100 / 100	334 ms	936 KiB

restore

#include <bits/stdc++.h>
using namespace std;

vector < pair <int , int> > adiacenta[5001];
int limita[5001];

int main ()
{
    ios :: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    int numar_noduri , numar_restrictii;
    cin >> numar_noduri >> numar_restrictii;

    for (int indice = 0 ; indice < numar_noduri ; indice++)
    {
        adiacenta[indice].emplace_back(indice + 1 , 1);
        adiacenta[indice + 1].emplace_back(indice , 0);
    }

    while (numar_restrictii--)
    {
        int stanga , dreapta , factor , valoare;
        cin >> stanga >> dreapta >> factor >> valoare;

        dreapta++;
        if (valoare == 1)
            { adiacenta[stanga].emplace_back(dreapta , factor - 1); }
        else
            { adiacenta[dreapta].emplace_back(stanga , -factor); }
    }

    for (int indice = 0 ; indice <= numar_noduri ; indice++)
        { limita[indice] = 1000000000; }

    limita[0] = 0;
    for (int repetare = 0 ; repetare <= numar_noduri ; repetare++)
    {
        bool gasit = false;
        for (int nod = 0 ; nod <= numar_noduri ; nod++) {
            for (auto& vecin : adiacenta[nod]) {
                if (limita[vecin.first] > limita[nod] + vecin.second)
                {
                    limita[vecin.first] = limita[nod] + vecin.second;
                    gasit = true;
                }
            }
        }

        if (repetare == numar_noduri && gasit)
            { cout << "-1"; return 0; }

        if (!gasit)
            { break; }
    }

    for (int indice = 0 ; indice < numar_noduri ; indice++)
        { cout << (limita[indice] == limita[indice + 1] ? "1 " : "0 "); }

    return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 13 / 13
• Subtask 3: 25 / 25
• Subtask 4: 55 / 55