제출 #100564

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
100564		alexpetrescu	열대 식물원 (Tropical Garden) (IOI11_garden)	C++14	100 / 100	4413 ms	22984 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <vector>

#define MAXN 150000
#define MAXK 300000
#define MAXQ 2000

int ans[MAXQ];
std::vector < int > g[MAXK + 1];
int muchie[MAXN][2], t[MAXK + 1];
int id[MAXN][2], h[MAXK + 1];
bool viz[MAXK + 1];

inline void avem(int x, int y) {
    if (muchie[x][0] == -1)
        muchie[x][0] = y;
    else if (muchie[x][1] == -1)
        muchie[x][1] = y;
}

inline void getPapa(int x, int r) {
    if (muchie[muchie[x][r]][0] != x) {
        t[id[x][r]] = id[muchie[x][r]][0];
        g[t[id[x][r]]].push_back(id[x][r]);
    } else {
        t[id[x][r]] = id[muchie[x][r]][1];
        g[t[id[x][r]]].push_back(id[x][r]);
    }
}

void dfs(int x) {
    viz[x] = 1;
    for (auto &y : g[x]) {
        if (viz[y] == 0) {
            h[y] = h[x] + 1;
            dfs(y);
        }
    }
}

inline void solve(int s, int n, int q, int k[], int N) {
    for (int i = 1; i <= n; i++)
        viz[i] = 0;
    int x = s, cnt = 0;
    while (viz[x] == 0) {
        viz[x] = 1;
        h[x] = 0;
        cnt++;
        x = t[x];
    }
    if (x == s) {
        int len = cnt;
        while (cnt > 0) {
            cnt--;
            x = t[x];
            h[x] = cnt;
            dfs(x);
        }
        for (int i = 0; i < q; i++)
            for (int j = 0; j < N; j++)
                if (viz[id[j][0]] && k[i] >= h[id[j][0]])
                    ans[i] += (k[i] - h[id[j][0]]) % len == 0;
    } else {
        dfs(s);
        for (int i = 0; i < q; i++)
            for (int j = 0; j < N; j++)
                if (viz[id[j][0]] && h[id[j][0]])
                    ans[i] += k[i] == h[id[j][0]];
    }
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
    for (int i = 0; i < N; i++)
        muchie[i][0] = muchie[i][1] = -1;
    for (int i = 0; i < M; i++) {
        int x = R[i][0], y = R[i][1];
        avem(x, y);
        avem(y, x);
    }

    int k = 0;
    for (int i = 0; i < N; i++) {
        id[i][0] = ++k;
        if (muchie[i][1] == -1)
            muchie[i][1] = muchie[i][0], id[i][1] = k;
        else
            id[i][1] = ++k;
    }

    for (int i = 1; i <= k; i++)
        g[i].clear();

    for (int i = 0; i < N; i++) {
        getPapa(i, 0);
        getPapa(i, 1);
    }

    for (int i = 0; i < Q; i++)
        ans[i] = 0;

    solve(id[P][0], k, Q, G, N);
    if (id[P][1] != id[P][0])
        solve(id[P][1], k, Q, G, N);

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

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