24772023-01-13 11:42:17sztomiTom és Jerry2 (60)cpp11Wrong answer 9/60474ms18100 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";
                }
                elkapja = akt;
                break;
            }
            akt = elozo[akt];
            tav++;
        }

        cout << elkapja << "\n";
    }
    //cout << debug_s << "\n";
}
SubtaskSumTestVerdictTimeMemory
base9/60
1Accepted0/03ms1832 KiB
2Wrong answer0/09ms5040 KiB
3Wrong answer0/22ms2300 KiB
4Wrong answer0/22ms2520 KiB
5Wrong answer0/22ms2648 KiB
6Wrong answer0/32ms3152 KiB
7Wrong answer0/22ms3052 KiB
8Wrong answer0/23ms3088 KiB
9Wrong answer0/23ms3172 KiB
10Wrong answer0/33ms3572 KiB
11Wrong answer0/33ms3560 KiB
12Wrong answer0/34ms4112 KiB
13Wrong answer0/36ms4820 KiB
14Wrong answer0/38ms5316 KiB
15Wrong answer0/38ms5796 KiB
16Accepted3/39ms6464 KiB
17Accepted3/3107ms9624 KiB
18Accepted3/327ms15648 KiB
19Wrong answer0/430ms13220 KiB
20Wrong answer0/450ms18100 KiB
21Time limit exceeded0/5474ms9960 KiB
22Time limit exceeded0/5455ms11856 KiB