81832024-01-12 16:21:24FulopMateTom és Jerry2 (60)cpp17Hibás válasz 10/60469ms64840 KiB
#include <bits/stdc++.h>

using namespace std;

int n, m, T, q, E;
vector<vector<pair<int, bool>>> v;
vector<bool> elvago;
vector<int> ans;
vector<int> tomtav;
vector<int> t, l;
int timer = 0;

struct Call
{
    int x, elozo, d, tav;
};

void lajhar(int x = 0, int pa = -1){
    if(t[x] != -1)return;
    l[x] = t[x] = ++timer;
    int ch = 0;
    for(auto i:v[x]){
        if(i.first == pa)continue;
        if(t[i.first] != -1){
            l[x] = min(l[x], t[i.first]);
        } else {
            lajhar(i.first, x);
            l[x] = min(l[x], l[i.first]);
            ch++;
            if(l[i.first] >= t[x] && pa != -1){
                elvago[x] = true;
            }
        }
    }
    if(ch > 1 && pa == -1){
        elvago[x] = true;
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m>>T>>q>>E; T--; E--;
    v.assign(n, {});
    elvago.assign(n, 0);
    t.assign(n, -1); l.assign(n, 1e9);
    for(int i = 0; i < m; i++){
        int a, b, c; cin>>a>>b>>c; a--; b--; c--;
        v[a].push_back({b, c});
        v[b].push_back({a, c});
    }

    lajhar();

    tomtav.assign(n, -1);
    queue<int> tomqu;
    tomqu.push(T);
    tomtav[T] = 0;
    while(!tomqu.empty()){
        int x = tomqu.front();
        tomqu.pop();
        for(auto&i:v[x]){
            if(i.second && tomtav[i.first] == -1){
                tomtav[i.first] = tomtav[x]+1;
                tomqu.push(i.first);
            }
        }
    }

    for(int&i: tomtav)if(i == -1)i = 1e9;

    ans.assign(n, -2);
    queue<Call> qu;
    qu.push(Call{E, -1, -1000000000, 0});
    while(!qu.empty()){
        Call curr = qu.front();
        qu.pop();
        int x = curr.x, elozo = curr.elozo, tav = curr.tav, d = curr.d;
        if(ans[x] != -2) continue;
        if(d >= 0){
            ans[x] = elozo;
            for(auto&i:v[x]){
                qu.push(Call{i.first, elozo, d+1, tav+1});
            }
        }
        else if(!elvago[x]){
            ans[x] = -1;
            for(auto&i:v[x]){
                qu.push(Call{i.first, elozo, d+1, tav+1});
            }
        } else {
            int currr = -tomtav[x];
            if(currr > d){
                d = currr;
                elozo = x;
            }
            for(auto&i:v[x]){
                qu.push(Call{i.first, elozo, d+1, tav+1});
            }
        }
    }

    while(q--){
        int a; cin>>a; a--;
        cout<<ans[a]+1<<endl;
    }
    return 0;
}

/*

8 8 5 2 1
1 2 1
1 3 1
2 4 1
3 4 2
4 5 2
4 6 2
6 7 1
6 8 1
7 4



*/
RészfeladatÖsszpontTesztVerdiktIdőMemória
base10/60
1Hibás válasz0/03ms1828 KiB
2Futási hiba0/070ms64840 KiB
3Elfogadva2/23ms2252 KiB
4Hibás válasz0/23ms2472 KiB
5Hibás válasz0/23ms2696 KiB
6Hibás válasz0/33ms2904 KiB
7Hibás válasz0/23ms3024 KiB
8Hibás válasz0/24ms3608 KiB
9Hibás válasz0/23ms3320 KiB
10Hibás válasz0/34ms3604 KiB
11Hibás válasz0/34ms4092 KiB
12Hibás válasz0/37ms5280 KiB
13Hibás válasz0/38ms5416 KiB
14Hibás válasz0/310ms5848 KiB
15Hibás válasz0/313ms6668 KiB
16Hibás válasz0/314ms6736 KiB
17Elfogadva3/327ms8172 KiB
18Hibás válasz0/359ms12476 KiB
19Időlimit túllépés0/4469ms7940 KiB
20Hibás válasz0/479ms17564 KiB
21Hibás válasz0/556ms14096 KiB
22Elfogadva5/581ms16956 KiB