Submission #99504

#	Time	Username	Problem	Language	Result	Execution time	Memory
99504		naoai	Tropical Garden (IOI11_garden)	C++14	69 / 100	5023 ms	82592 KiB

garden

#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"

using namespace std;

#define fin cin
#define fout cout
//ifstream fin("x.in"); ofstream fout("x.out");

typedef long long i64;
const int nmax = 15e4 + 5;
const int mmax = 2 * 15e4 + nmax + 5;
const int qmax = 2000;
const pair<int, int> nul = {-1, -1};

static vector<int> c[mmax + 1];
static pair<int, int> pe_ciclu[mmax + 1];
static int reprezentant[mmax + 1], h[mmax + 1];

static bool finalok[mmax + 1];

static vector<int> g[mmax + 1], gt[mmax + 1];
static vector<pair<int, int>> gorig[nmax + 1];

static int top, stk[mmax + 1];

static vector<pair<int, int>> qry[mmax + 1];
static int rasp[qmax + 1];

bool cmp (pair<int, int> a, pair<int, int> b) {
    return a.second < b.second;
}

int best (int nod, int indm) {
    if (gorig[nod].size() == 1)
        return gorig[nod][0].second;
    if (gorig[nod][0].second / 2 != indm / 2)
        return gorig[nod][0].second;
    else
        return gorig[nod][1].second;
}

void fa_graf (int N, int &M, int P, int R[][2], int Q, int G[]) {
    for (int i = 0; i < M; ++ i) {
        gorig[R[i][0]].push_back({R[i][1], 2 * i});
        gorig[R[i][1]].push_back({R[i][0], 2 * i + 1});

        if (R[i][1] == P)
            finalok[2 * i] = 1;
        if (R[i][0] == P)
            finalok[2 * i + 1] = 1;
    }

    for (int i = 0; i < N; ++ i) {
        sort(gorig[i].begin(), gorig[i].end(), cmp);
    }

    // muchiile de functie
    for (int i = 0; i < M; ++ i) {
        int find_edge = best(R[i][1], 2 * i);
        g[2 * i].push_back(find_edge);

        find_edge = best(R[i][0], 2 * i + 1);
        g[2 * i + 1].push_back(find_edge);
    }

    // 0 ... 2M - 1 sunt muchiile
    // 2M... 2M + N - 1 sunt nodurile de start

    // adauga noduri suplimentare de start
    for (int i = 0; i < N; ++ i) {
        if (gorig[i].size())
            g[2 * M + i].push_back(gorig[i][0].second);
    }

    M *= 2;
}

void ciclu (int nod, int tata, int ind) {
    c[ind].push_back(nod);
    pe_ciclu[nod] = {ind, c[ind].size() - 1};

    for (auto i : g[nod]) {
        if (pe_ciclu[i] != nul && pe_ciclu[i].first != ind) {
            ciclu(i, nod, ind);
        }
    }
}

int cauta_ciclii (int N) {
    // sortare topologica ca sa scot arborii
    vector<int> grad(N, 0);
    for (int i = 0; i < N; ++ i) {
        for (auto j : g[i])
            ++ grad[j];
    }

    queue<int> q;
    for (int i = 0; i < N; ++ i) {
        if (grad[i] == 0)
            q.push(i);
    }

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

        pe_ciclu[x] = {-1, -1};
        for (auto i : g[x]) {
            -- grad[i];
            if (grad[i] == 0)
                q.push(i);
        }
    }

    // determin care sunt ciclii
    int cycles = 0;
    for (int i = 0; i < N; ++ i) {
        if (pe_ciclu[i] != nul && pe_ciclu[i].first == 0) {
            ++ cycles;
            ciclu(i, -1, cycles);
        }
    }
    return cycles;
}

void dfs (int nod, int tata) {
    for (auto i : gt[nod]) {
        if (pe_ciclu[i] == nul && i != tata) {
            reprezentant[i] = reprezentant[nod];
            h[i] = h[nod] + 1;
            dfs(i, nod);
        }
    }
}

void det_arbori (int N, int cnt) {
    for (int i = 0; i < N; ++ i) {
        for (auto j : g[i]) {
            gt[j].push_back(i);
        }
    }

    for (int u = 1; u <= cnt; ++ u) {
        for (auto i : c[u]) {
            reprezentant[i] = i;
            dfs(i, -1);
        }
    }
}

void solve (int nod, int tata) {
    stk[top ++] = nod;
    for (auto i : qry[nod]) {
        rasp[i.second] += finalok[stk[i.first]];
    }

    for (auto i : gt[nod]) {
        if (pe_ciclu[i] == nul && i != tata) {
            solve(i, nod);
        }
    }

    -- top;
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    fa_graf(N, M, P, R, Q, G);
    int cnt = cauta_ciclii(M + N);
    det_arbori(M + N, cnt);

    for (int i = 0; i < Q; ++ i) {
        for (int j = M; j < M + N; ++ j) {
            // pot ajunge de la j in g[i] pasi la o muchie care da in nodul P?

            if (G[i] >= h[j]) { // intru pe ciclu
                pair<int, int> pos = pe_ciclu[reprezentant[j]];
                int final_node = c[pos.first][(pos.second + G[i] - h[j]) % c[pos.first].size()];

                if (finalok[final_node] == 1)
                    ++ rasp[i];
            } else { // tre sa ridic j cu G[i]
                qry[j].push_back({h[j] - G[i], i});
            }
        }
    }

    for (int i = 1; i <= cnt; ++ i) {
        for (auto j : c[i]) {
            solve(j, -1);
        }
    }

    for(int i = 0; i < Q; i ++)
        answer(rasp[i]);
}

• Subtask 1: 49 / 49
• Subtask 2: 20 / 20
• Subtask 3: 0 / 31