Rezultati

Up. imeNalogaJezikRezultatČas oddaje
Aquasonic-2018 Nič nas ne sme presenetiti! C++ 100/100OK 19. apr '18 @ 18:04

Test Točke Porabljen spomin Porabljen čas Status
#1 12/12 5,484 MiB 0,000 s OK
#2 12/12 5,492 MiB 0,033 s OK
#3 12/12 5,488 MiB 0,000 s OK
#4 12/12 14,496 MiB 0,435 s OK
#5 13/13 5,484 MiB 0,004 s OK
#6 13/13 13,867 MiB 0,161 s OK
#7 13/13 9,398 MiB 0,213 s OK
#8 13/13 9,430 MiB 0,176 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;

typedef pair<int, int> pii;

const int maxn = 1 * 1e5 + 17;

int N, Q, leaf, sz;
int vtxidx;
int in[maxn], out[maxn];

vector<pii> vtx;
/// int parent[maxn], sz[maxn];

bool vis[maxn];

vector<int> graph[maxn];

void DFS(int u, int p)
{
    in[u] = ++sz;

    for (int v : graph[u])
        if (v != p)
            DFS(v, u);

    out[u] = sz;
}

map<pii, bool> edge;

/**
void DFS2(int idx, int lastv)
{
    printf("AT %d INLAST %d\n", idx, lastv);
    printf("FIND %d %d\n", vtx[vtxidx].f, vtx[vtxidx].s);

    int v = lastv;

    for (int i = 0; i < graph[idx].size(); i++) {

        printf("CHECKING %d ... in = %d\n", graph[idx][i], in[graph[idx][i]]);

        if (graph[idx][i] == vtx[vtxidx].s) {
            assert(graph[idx][i] == vtx[vtxidx].s);
            vtxidx++;
            match++;
            DFS(graph[idx][i], v);
        }

        if (graph[idx][i] > vtx[vtxidx].s) {
            break;
        }
    }
}
**/

/**
int find(int x)
{
    if (parent[x] == x) return x;
    return parent[x] = find(parent[x]);
}

void merge(int x, int y)
{
    x = find(x); y = find(y);

    if (x == y) return;

    if (sz[x] < sz[y]) swap(x, y);

    sz[x] += sz[y];
    parent[y] = x;
}
**/

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

    scanf("%d %d", &N, &Q);

    for (int i = 1; i < N; i++) {
        int A, B; scanf("%d %d", &A, &B);
        graph[A].pb(B); graph[B].pb(A);
    }

    for (int i = 1; i <= N; i++) {
        if (graph[i].size() == 1) {
            leaf = i;
            break;
        }
    }

    DFS(leaf, leaf);

/// for (int i = 1; i <= N; i++) printf("%d: %d %d\n", i, in[i], out[i]);

    while (Q--) {
        int count; scanf("%d", &count);
        vtx.clear(); map<int, int> cv;
        for (int i = 0; i < count; i++) {
            int A; scanf("%d", &A);
            vtx.pb(mp(in[A], A));
            cv[A] = 1;
        }
        
        sort(vtx.begin(), vtx.end());

        cv[vtx[0].s] = 2;

        bool cont = false;

        for (int i = 1; i < vtx.size(); i++) {
            bool fnd = false;
            for (int j = 0; j < graph[vtx[i].s].size(); j++)  {
                if (cv[graph[vtx[i].s][j]] == 2) {
                    cv[vtx[i].s] = 2;
                    fnd = true;
                    break;
                }
            }

            if (!fnd) {
                puts("NASLEDNJI"); cont = true;
                break;
            }
        }

        if (cont) continue;

        puts("ALAAAARHM");


        /**
        ans = true;
        vtxidx = 1; match = 1;
        DFS2(vtx[0].s, vtx[1].f);

        if (match == count) {
            cout << "DA" << endl;
        } else {
            cout << "NE" << endl;
        }
        **/
    }

    return 0;
}