24792023-01-13 11:59:34sztomiTom és Jerry2 (60)cpp11Hibás válasz 9/60538ms18508 KiB
#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9+7;

void dfs(int akt, int szulo, vector<vector<int>>& graf, vector<int>& be_ido, vector<int>& kis_ido, vector<bool>& volt, int& ido, vector<bool>& vagok){
    volt[akt] = true;
    be_ido[akt] = kis_ido[akt] = ido++;
    int gyerek = 0;
    for(int kov : graf[akt]){
        if(kov == szulo) continue;
        if(volt[kov]){
            kis_ido[akt] = min(kis_ido[akt], be_ido[kov]);
        }
        else{
            dfs(kov, akt, graf, be_ido, kis_ido, volt, ido, vagok);
            kis_ido[akt] = min(kis_ido[akt], kis_ido[kov]);
            if(kis_ido[kov] >= be_ido[akt] && szulo != -1){
                vagok[akt] = true;
            }
            gyerek++;
        }
    }
    if(szulo == -1 && gyerek > 1){
        vagok[akt] = true;
    }
}

vector<bool> vago_keres(vector<vector<int>>& graf, int n){
    int ido = 0;
    vector<int> be_ido(n+1, -1);
    vector<int> kis_ido(n+1, -1);
    vector<bool> volt(n+1, false);
    vector<bool> vagok(n+1, false);
    for(int i = 1; i <= n; i++){
        if(!volt[i]){
            dfs(i, -1, graf, be_ido, kis_ido, volt, ido, vagok);
        }
    }

    return vagok;
}

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

    int n, m, tom_kezd, jerry_db, lyuk;
    cin >> n >> m >> tom_kezd >> jerry_db >> lyuk;
    vector<vector<int>> tom_graf(n+1, vector<int>());
    vector<vector<int>> jerry_graf(n+1, vector<int>());
    int a, b, c;
    for(int i = 0; i < m; i++){
        cin >> a >> b >> c;
        jerry_graf[a].push_back(b);
        jerry_graf[b].push_back(a);

        if(c == 2){
            tom_graf[a].push_back(b);
            tom_graf[b].push_back(a);
        }
    }

    // lyukba a legrovidebb ut
    vector<int> elozo(n+1, -1);
    vector<bool> volt(n+1, false);

    queue<int> q;
    q.push(lyuk);
    volt[lyuk] = true;
    int akt, akt_meret = 1, kov_meret = 0;
    while(!q.empty()){
        akt = q.front();
        q.pop();
        akt_meret--;

        for(int x : jerry_graf[akt]){
            if(volt[x]) continue;
            q.push(x);
            kov_meret++;
            volt[x] = true;
            elozo[x] = akt;
        }

        if(akt_meret == 0){
            swap(akt_meret, kov_meret);
        }
    }

    while(!q.empty()) q.pop();
    vector<int> tom_tav(n+1, INF);
    tom_tav[tom_kezd] = 0;
    q.push(tom_kezd);
    while(!q.empty()){
        akt = q.front();
        q.pop();
        if(akt == lyuk) continue;

        for(int x : tom_graf[akt]){
            if(tom_tav[x] != INF) continue;
            q.push(x);
            tom_tav[x] = tom_tav[akt] + 1;
        }
    }

    vector<bool> vago = vago_keres(jerry_graf, n);
    /*
    cout << "vagok: ";
    for(int i = 1; i <= n; i++){
        if(vago[i]) cout << i << " ";
    }
    cout << "\n";

    cout << "tom_tav: ";
    for(int i = 1; i <= n; i++){
        cout << "(" << i << ", " << tom_tav[i] << ") ";
    }
    cout << "\n";
    */

    string debug_s = "d_kezd\n";
    for(int i = 0; i < jerry_db; i++){
        // ha a legrovidebb uton at kell haladjon olyan vagopontokon, ahova tom hamarabb vagy ugyanakkor odaer

        bool debug = i == 5014;

        int akt;
        int tav = 0;
        int elkapja = 0;
        cin >> akt;
        while(akt != lyuk){
            //cout << "itt jar " << akt << " tav: " << tav << " tom_tav: " << tom_tav[akt] << "\n";
            if(vago[akt] && tom_tav[akt] < tav){
                if(debug){
                    debug_s += to_string(akt) + " " + to_string(tom_tav[akt]) + " " + to_string(tav) + "\n";
                }
                if(elkapja == 0 || (elkapja != 0 && akt < elkapja)){
                    elkapja = akt;
                }
            }
            akt = elozo[akt];
            tav++;
        }

        cout << elkapja << "\n";
    }
    //cout << debug_s << "\n";
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base9/60
1Elfogadva0/03ms2100 KiB
2Hibás válasz0/09ms5304 KiB
3Hibás válasz0/22ms2272 KiB
4Hibás válasz0/22ms2732 KiB
5Hibás válasz0/22ms2788 KiB
6Hibás válasz0/32ms3000 KiB
7Hibás válasz0/22ms3104 KiB
8Hibás válasz0/23ms3448 KiB
9Hibás válasz0/23ms3648 KiB
10Hibás válasz0/33ms3940 KiB
11Hibás válasz0/33ms4300 KiB
12Hibás válasz0/34ms4552 KiB
13Hibás válasz0/36ms5616 KiB
14Hibás válasz0/37ms6148 KiB
15Hibás válasz0/38ms6524 KiB
16Elfogadva3/39ms6812 KiB
17Elfogadva3/3272ms10144 KiB
18Elfogadva3/329ms16088 KiB
19Hibás válasz0/432ms13628 KiB
20Hibás válasz0/446ms18508 KiB
21Időlimit túllépés0/5455ms10360 KiB
22Időlimit túllépés0/5538ms12380 KiB