8183 2024. 01. 12 16:21:24 FulopMate Tom és Jerry2 (60) cpp17 Hibás válasz 10/60 469ms 64840 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 Összpont Teszt Verdikt Idő Memória
base 10/60
1 Hibás válasz 0/0 3ms 1828 KiB
2 Futási hiba 0/0 70ms 64840 KiB
3 Elfogadva 2/2 3ms 2252 KiB
4 Hibás válasz 0/2 3ms 2472 KiB
5 Hibás válasz 0/2 3ms 2696 KiB
6 Hibás válasz 0/3 3ms 2904 KiB
7 Hibás válasz 0/2 3ms 3024 KiB
8 Hibás válasz 0/2 4ms 3608 KiB
9 Hibás válasz 0/2 3ms 3320 KiB
10 Hibás válasz 0/3 4ms 3604 KiB
11 Hibás válasz 0/3 4ms 4092 KiB
12 Hibás válasz 0/3 7ms 5280 KiB
13 Hibás válasz 0/3 8ms 5416 KiB
14 Hibás válasz 0/3 10ms 5848 KiB
15 Hibás válasz 0/3 13ms 6668 KiB
16 Hibás válasz 0/3 14ms 6736 KiB
17 Elfogadva 3/3 27ms 8172 KiB
18 Hibás válasz 0/3 59ms 12476 KiB
19 Időlimit túllépés 0/4 469ms 7940 KiB
20 Hibás válasz 0/4 79ms 17564 KiB
21 Hibás válasz 0/5 56ms 14096 KiB
22 Elfogadva 5/5 81ms 16956 KiB