oj.uz

Submission #1022665

# Submission time Handle Problem Language Result Execution time Memory
1022665 2024-07-13T21:59:10 Z PanosPask Tropical Garden (IOI11_garden) C++14
69 / 100
 46 ms 17404 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
#define pb push_back

using namespace std;

const int MAXUP = 30;

int N, Q;
vector<int> queries;
vector<vector<int>> adj_list;

/*target[up][x]
 * x = 2 * i: The 2^up target of i if we reached i without going through the most beautiful path.
 * x = 2 * i + 1: The 2^up target of i if we reached i by going through the most beautiful path. 
 */
vector<int> target;

/*dist[i]:
 *Distance from i to the current destination (either 2 * P or 2 * P + 1)
 */
vector<int> dist;

// Variables used for cycle finding
vector<bool> on_stack;
vector<bool> visited;
int cur = 0, len = 0;

// Variables used for finding number of nodes that end at dest after some moves
vector<int> freq;
vector<int> freqmodlen;

// Final answer for each query
vector<int> ans;

// Returns distance from node to dest (2 * N if dest cannot be reached from node)
int dfs(int node, int dest)
{
    if (visited[node]) {
        if (on_stack[node]) {
            // New cycle
            // Check if destination is inside this new cycle
            // Since dfs started on dest, the completed cycle must also end on dest

            if (node == dest) {
                // dest belongs to this cycle
                len = cur;
                return 0;
            }
            else {
                // dest does not belong to a cycle
                return 2 * N;
            }
        }
        else {
            return dist[node];
        }
    }

    visited[node] = on_stack[node] = true;
    cur++;

    dist[node] = min(2 * N, dfs(target[node], dest) + 1);
    if (node == dest) {
        dist[node] = 0;
    }

    if (node % 2 == 0) {
        // We only care about even numbered nodes because they represent the starting positions
        freq[dist[node]]++;
    }

    on_stack[node] = false;
    cur--;

    return dist[node];
}

void process_destination(int t)
{
    visited.assign(2 * N, false);
    on_stack.assign(2 * N, false);
    dist.assign(2 * N + 1, 2 * N);
    len = cur = 0;
    freq.assign(2 * N + 1, 0);

    dfs(t, t);
    for (int i = 0; i < 2 * N; i++) {
        if (!visited[i]) {
            dfs(i, t);
        }
    }

    freqmodlen.assign(len, 0);

    int steps = 0;
    for (int i = 0; i < Q; i++) {
        while (steps < min(2 * N, queries[i])) {
            // Add new step
            if (len) {
                freqmodlen[steps % len] += freq[steps];
            }
            steps++;
        }

        if (queries[i] < 2 * N) {
            ans[i] += freq[queries[i]];
        }
        if (len) {
            ans[i] += freqmodlen[queries[i] % len];
        }
    }
}

void add_target(int fr, int to)
{
    if (adj_list[to][0] == fr / 2) {
        target[fr] = 2 * to + 1;
    }
    else {
        target[fr] = 2 * to;
    }
}

void count_routes(int n, int M, int P, int R[][2], int q, int G[])
{
    N = n;
    Q = q;

    queries.resize(Q);
    ans.assign(Q, 0);
    adj_list.resize(N);
    target.resize(2 * N);

    for (int i = 0; i < Q; i++) {
        queries[i] = G[i];
    }

    for (int i = 0; i < M; i++) {
        adj_list[R[i][0]].pb(R[i][1]);
        adj_list[R[i][1]].pb(R[i][0]);
    }


    for (int i = 0; i < N; i++) {
        add_target(2 * i, adj_list[i][0]);

        if (adj_list[i].size() >= 2) {
            add_target(2 * i + 1, adj_list[i][1]);
        }
        else {
            add_target(2 * i + 1, adj_list[i][0]);
        }
    }

    process_destination(2 * P);
    process_destination(2 * P + 1);

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

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 440 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 2 ms 608 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 440 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 2 ms 608 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 7 ms 2852 KB Output is correct
12 Correct 14 ms 4700 KB Output is correct
13 Correct 25 ms 17404 KB Output is correct
14 Correct 44 ms 13908 KB Output is correct
15 Correct 45 ms 14192 KB Output is correct
16 Correct 38 ms 10928 KB Output is correct
17 Correct 41 ms 9552 KB Output is correct
18 Correct 15 ms 4440 KB Output is correct
19 Correct 45 ms 13912 KB Output is correct
20 Correct 45 ms 14308 KB Output is correct
21 Correct 38 ms 10576 KB Output is correct
22 Correct 36 ms 9668 KB Output is correct
23 Correct 46 ms 15440 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 440 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 2 ms 608 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 7 ms 2852 KB Output is correct
12 Correct 14 ms 4700 KB Output is correct
13 Correct 25 ms 17404 KB Output is correct
14 Correct 44 ms 13908 KB Output is correct
15 Correct 45 ms 14192 KB Output is correct
16 Correct 38 ms 10928 KB Output is correct
17 Correct 41 ms 9552 KB Output is correct
18 Correct 15 ms 4440 KB Output is correct
19 Correct 45 ms 13912 KB Output is correct
20 Correct 45 ms 14308 KB Output is correct
21 Correct 38 ms 10576 KB Output is correct
22 Correct 36 ms 9668 KB Output is correct
23 Correct 46 ms 15440 KB Output is correct
24 Incorrect 1 ms 352 KB Output isn't correct
25 Halted 0 ms 0 KB -