Rezultati

Up. imeNalogaJezikRezultatČas oddaje
ognjeniprocesor-2018 Prehitevanje C++ 100/100OK 04. okt '18 @ 19:48

Test Točke Porabljen spomin Porabljen čas Status
#1 16/16 3,074 MiB 0,004 s OK
#2 16/16 3,195 MiB 0,004 s OK
#3 17/17 3,043 MiB 0,000 s OK
#4 17/17 4,691 MiB 1,093 s OK
#5 17/17 35,336 MiB 2,277 s OK
#6 17/17 3,070 MiB 0,000 s OK

Ocenjevani program (prehitevanje.cpp):
#include<iostream>
#include<string>
#include<unordered_map>
#include<vector>
using namespace std;

int main() {
    int N;
    cin >> N;
    string tekm;
    unordered_map<string,vector<string>> vrstni_red;
    cin >> tekm;
    string prvi = tekm;
    string prev = tekm;
    vector<string> tmp = {""};
    vrstni_red.emplace(tekm, tmp);
    for (int i = 1; i < N; ++i) {
        cin >> tekm;
        vrstni_red[prev].push_back(tekm);
        vector<string> tmp = {prev};
        vrstni_red.emplace(tekm, tmp);
        prev = tekm;
        if (i ==  N-1) vrstni_red[tekm].push_back("");
    }
    
    int P;
    cin >> P;
    for (int i = 0; i < P; ++i) {
        string X, Y;
        cin >> X >> Y;
        if (vrstni_red[Y][0] == X) continue;
        if (prvi == Y) prvi = X;
        else if (prvi == X && Y != vrstni_red[X][1]) prvi = vrstni_red[X][1];
        
        string predX, poX, predY, poY;
        predX = vrstni_red[X][0]; poX = vrstni_red[X][1];
        if (predX != "") { 
            tmp = {vrstni_red[predX][0], poX};
            vrstni_red[predX] = tmp;
        }
        if (poX != "") { 
            tmp = {predX, vrstni_red[poX][1]};
            vrstni_red[poX] = tmp;
        }
        predY = vrstni_red[Y][0]; poY = vrstni_red[Y][1];
//         cout << "print predY,  poY " << predY << " " << poY << "\n";
        if (predY != "") { 
            tmp = {vrstni_red[predY][0], X};
            vrstni_red[predY] = tmp;
        }
        tmp = {predY, Y};
        vrstni_red[X] = tmp;
        tmp = {X, vrstni_red[Y][1]};
        vrstni_red[Y] = tmp;
    }
    
//     cout << "--------------------------\n";
//     cout << "prvi: " << prvi << "\n"; 
//     for (auto elem : vrstni_red) {
//         cout << "tekmovalec: " << elem.first <<  "\n"; 
//         cout << "soseda: " << elem.second[0] << " " << elem.second[1] << "\n";
//     }
//     
    int cnt = 1;
    prev = prvi;
    while (cnt < N) {
        cout << prev << "\n";
        prev = vrstni_red[prev][1];
        ++cnt;
    }
    cout << prev << "\n";
}