oj.uz

Submission #100563

# Submission time Handle Problem Language Result Execution time Memory
100563 2019-03-12T10:13:24 Z alexpetrescu Tropical Garden (IOI11_garden) C++14
0 / 100
 9 ms 7580 KB 
#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[]) {
    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 = 1; 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 = 1; 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);
    if (id[P][1] != id[P][0])
        solve(id[P][1], k, Q, G);

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

Subtask #1
0 / 49.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 7580 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 7580 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 7580 KB Output isn't correct
2 Halted 0 ms 0 KB -