Rezultati

Up. imeNalogaJezikRezultatČas oddaje
Aquasonic-2018 Dolenjec C++ 100/100OK 10. maj '18 @ 16:51

Test Točke Porabljen spomin Porabljen čas Status
#1 3/3 12,523 MiB 0,004 s OK
#2 3/3 12,520 MiB 0,016 s OK
#3 3/3 12,523 MiB 0,004 s OK
#4 3/3 12,383 MiB 0,016 s OK
#5 3/3 12,523 MiB 0,000 s OK
#6 3/3 12,391 MiB 0,010 s OK
#7 3/3 12,391 MiB 0,004 s OK
#8 3/3 12,391 MiB 0,000 s OK
#9 3/3 12,523 MiB 0,004 s OK
#10 3/3 12,523 MiB 0,010 s OK
#11 3/3 12,520 MiB 0,004 s OK
#12 3/3 12,516 MiB 0,000 s OK
#13 3/3 12,527 MiB 0,004 s OK
#14 3/3 12,387 MiB 0,000 s OK
#15 3/3 12,527 MiB 0,004 s OK
#16 3/3 12,395 MiB 0,004 s OK
#17 3/3 12,395 MiB 0,010 s OK
#18 3/3 12,426 MiB 0,010 s OK
#19 3/3 12,422 MiB 0,010 s OK
#20 3/3 12,414 MiB 0,004 s OK
#21 3/3 12,555 MiB 0,010 s OK
#22 3/3 12,566 MiB 0,010 s OK
#23 3/3 29,254 MiB 0,398 s OK
#24 3/3 24,918 MiB 0,313 s OK
#25 3/3 25,488 MiB 0,356 s OK
#26 3/3 18,297 MiB 0,224 s OK
#27 3/3 16,145 MiB 0,152 s OK
#28 3/3 26,746 MiB 0,356 s OK
#29 3/3 25,223 MiB 0,344 s OK
#30 3/3 18,512 MiB 0,181 s OK
#31 3/3 16,020 MiB 0,152 s OK
#32 3/3 15,195 MiB 0,122 s OK
#33 4/4 12,523 MiB 0,010 s OK

Ocenjevani program (main.cpp):
#include <bits/stdc++.h>

#define f first
#define s second
#define mp make_pair
#define pb push_back

#define left(x) ((x) << 1)
#define right(x) ((x) << 1 | 1)
#define mid(x, y) ((x) + (y) >> 1)

using namespace std;

const int maxn = 1 * 1e5 + 17;

int N, M, K, S;
int comp[maxn];


bool vis[maxn], spec[maxn], csp[maxn];

vector<int> graph[maxn], rgraph[maxn];
vector<int> cgraph[maxn];

int sz;
vector<int> scc[maxn];

stack<int> tsort;

void DFS(int u)
{
    vis[u] = true;

    for (int v : graph[u])
        if (!vis[v])
            DFS(v);

    tsort.push(u);
}

void DFSC(int u)
{
    if (csp[u]) printf("DA\n"), exit(0);

    for (int v : cgraph[u])
        DFSC(v);
}

int main()
{
    ios_base::sync_with_stdio(false);

    cin >> N >> M >> K >> S;
    for (int i = 0; i < K; i++) {
        int A; cin >> A;
        spec[A] = true;
    }

    for (int i = 0; i < M; i++) {
        int A, B; cin >> A >> B;
        graph[A].pb(B);
        rgraph[B].pb(A);
    }

    for (int i = 1; i <= N; i++)
        sort(graph[i].begin(), graph[i].end()),
        graph[i].erase(unique(graph[i].begin(), graph[i].end()), graph[i].end()),
        sort(rgraph[i].begin(), rgraph[i].end()),
        rgraph[i].erase(unique(rgraph[i].begin(), rgraph[i].end()), rgraph[i].end());

    for (int i = 1; i <= N; i++)
        if (!vis[i])
            DFS(i);

    memset(vis, 0, sizeof vis);

    while (!tsort.empty()) {
        int w = tsort.top(); tsort.pop();
        /// cout << w << " ";

        if (vis[w]) continue;

        sz++;
        queue<int> q; q.push(w);

        while (!q.empty()) {
            int u = q.front(); q.pop();

            if (vis[u]) continue;

            comp[u] = sz;
            vis[u] = true;
            scc[sz].pb(u);

            for (int v : rgraph[u])
                if (!vis[v])
                    q.push(v);
        }

        /**
        
        printf("%d: ", sz);
        for (int v : scc[sz]) printf("%d ", v);
        printf("\n");
        **/
        
    }

    for (int i = 1; i <= sz; i++)
        for (int v : scc[i])
            for (int u : graph[v])
                if (comp[u] != i)
                    cgraph[i].pb(comp[u]);

    for (int i = 1; i <= sz; i++)
        sort(cgraph[i].begin(), cgraph[i].end()),
        cgraph[i].erase(unique(cgraph[i].begin(), cgraph[i].end()), cgraph[i].end());

    for (int i = 1; i <= sz; i++) {
        if (scc[i].size() == 1) {
            int u = scc[i][0];
            if (!spec[u]) continue;

            auto x = find(graph[u].begin(), graph[u].end(), u);

            if (x != graph[u].end()) csp[i] = true;
        } else {
            for (int j = 0; j < scc[i].size() && !csp[i]; j++)
            /// printf("... %d\n", scc[i][j]),
                csp[i] |= spec[scc[i][j]];
        }
    }

    DFSC(comp[S]);

    printf("NE\n");

/**
6 7 1 1
1
1 2
2 3
3 4
4 2
4 5
5 6
6 4

**/

/**
    for (int i = 1; i <= sz; i++)
        printf("%d ", csp[i]);
**/

/**
    for (int i = 1; i <= sz; i++, puts(""))
        for (int v : cgraph[i])
            printf("%d ", v);
**/

    return 0;
}