8106 2024. 01. 12 13:36:58 EsVagy Tom és Jerry2 (60) cpp17 Hibás válasz 24/60 43ms 12244 KiB
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <climits>
#include <queue>
#include <fstream>
#include <sstream>
#include <math.h>
#include <list>

using namespace std;

using ll = long long;

struct node
{
    int tomDist = -1;
    int branch = -1;
    int wrongNode = -1;
};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, t, j, h;
    cin >> n >> m >> t >> j >> h;
    t--; h--;
    vector<node> nodes(n, node());
    vector<vector<int>> tomEdges(n, vector<int>());
    vector<vector<int>> jerryEdges(n, vector<int>());
    vector<bool> visited(n, false);
    vector<bool> accessibleByTom(n, false);
    for (int i = 0; i < m; i++)
    {
        int a, b, w;
        cin >> a >> b >> w;
        a--; b--;
        if (w == 2)
        {
            tomEdges[a].push_back(b);
            tomEdges[b].push_back(a);
        }
        jerryEdges[a].push_back(b);
        jerryEdges[b].push_back(a);
    }

    queue<int> tomQueue;
    tomQueue.push(t);
    nodes[t].tomDist = 0;
    set<int> validBranches;
    accessibleByTom[t] = true;
    while (!tomQueue.empty())
    {
        int next = tomQueue.front();
        tomQueue.pop();
        for (int neigh : tomEdges[next])
        {
            if (neigh != h && nodes[neigh].tomDist == -1)
            {
                nodes[neigh].tomDist = nodes[next].tomDist + 1;
                tomQueue.push(neigh);
                accessibleByTom[neigh] = true;
            }
        }
    }

    queue<int> q;
    q.push(h);
    visited[h] = true;
    int branch = 0;
    while (!q.empty())
    {
        int next = q.front();
        q.pop();
        if (nodes[next].tomDist != -1 && nodes[next].branch == -1)
        {
            nodes[next].branch = branch;
            branch++;
            nodes[next].wrongNode = next;
        }
        bool isBranch = nodes[next].branch != -1;
        for (int neigh : jerryEdges[next])
        {
            if (!visited[neigh])
            {
                if (isBranch)
                {
                    nodes[neigh].branch = nodes[next].branch;
                    nodes[neigh].tomDist = max(0, nodes[next].tomDist - 1);
                    nodes[neigh].wrongNode = nodes[next].wrongNode;
                }
                q.push(neigh);
                visited[neigh] = true;
            }
            else
            {
                if (!accessibleByTom[next] && !accessibleByTom[neigh] && nodes[neigh].branch != nodes[next].branch)
                {
                    if (nodes[next].branch != -1)
                    {
                        validBranches.insert(nodes[next].branch);
                    }
                    if (nodes[neigh].branch != -1)
                    {
                        validBranches.insert(nodes[neigh].branch);
                    }
                }                
            }
        }
    }

    for (int i = 0; i < j; i++)
    {
        int nextNode;
        cin >> nextNode;
        nextNode--;
        if (nodes[nextNode].branch == -1)
        {
            cout << "0\n";
        }
        else
        {
            if (validBranches.count(nodes[nextNode].branch) != 0)
            {
                cout << "0\n";
            }
            else
            {
                if (nodes[nextNode].tomDist > 0)
                {
                    cout << "0\n";
                }
                else
                {
                    cout << nodes[nextNode].wrongNode + 1 << "\n";
                }
            }
        }
    }
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 24/60
1 Elfogadva 0/0 3ms 2100 KiB
2 Hibás válasz 0/0 9ms 4596 KiB
3 Hibás válasz 0/2 3ms 2352 KiB
4 Hibás válasz 0/2 3ms 2456 KiB
5 Hibás válasz 0/2 3ms 2516 KiB
6 Hibás válasz 0/3 3ms 2732 KiB
7 Hibás válasz 0/2 3ms 3084 KiB
8 Hibás válasz 0/2 3ms 3056 KiB
9 Hibás válasz 0/2 3ms 3172 KiB
10 Hibás válasz 0/3 3ms 3392 KiB
11 Hibás válasz 0/3 3ms 3716 KiB
12 Hibás válasz 0/3 4ms 4088 KiB
13 Hibás válasz 0/3 6ms 4340 KiB
14 Hibás válasz 0/3 8ms 4928 KiB
15 Hibás válasz 0/3 8ms 5284 KiB
16 Hibás válasz 0/3 9ms 5376 KiB
17 Elfogadva 3/3 10ms 6452 KiB
18 Elfogadva 3/3 18ms 8732 KiB
19 Elfogadva 4/4 28ms 9644 KiB
20 Elfogadva 4/4 43ms 12244 KiB
21 Elfogadva 5/5 27ms 11332 KiB
22 Elfogadva 5/5 26ms 11540 KiB