제출 #1306971

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

restore

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

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

inline void Solve ()
{
    int numar_noduri , numar_muchii;
    cin >> numar_noduri >> numar_muchii;

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

    while (numar_muchii--)
    {
        int stanga , dreapta , termen , valoare;
        cin >> stanga >> dreapta >> termen >> valoare;

        stanga++;
        dreapta++;

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

    for (int ramas = numar_noduri - 1 ; ramas ; ramas--) {
        for (int nod = 0 ; nod <= numar_noduri ; nod++) {
            for (auto& vecin : adiacenta[nod])
                { distanta[vecin.first] = min(distanta[vecin.first] , distanta[nod] + vecin.second); }
        }
    }

    for (int nod = 0 ; nod <= numar_noduri ; nod++) {
        for (auto& vecin : adiacenta[nod]) {
            if (distanta[vecin.first] > distanta[nod] + vecin.second) 
                { cout << "-1"; return; }
        }
    }
    
    for (int indice = 1 ; indice <= numar_noduri ; indice++) 
        { cout << ((distanta[indice] - distanta[indice - 1]) ^ 1) << ' '; }
}

int main ()
{
    ios :: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int numar_teste = 1;
    // cin >> numar_teste;
    while (numar_teste--)
        { Solve(); }

    return 0;
}

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