oj.uz

Submission #1097411

# Submission time Handle Problem Language Result Execution time Memory
1097411 2024-10-07T08:32:49 Z VectorLi Tropical Garden (IOI11_garden) C++17
100 / 100
 1978 ms 38708 KB 
#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
#define long long long

using namespace std;

const int V = (int) 1.5E5;

int n, m, x;
vector<pair<int, int>> e[V];

int t[V];
int p[V * 2];
int d[V * 2];
bitset<V * 2> f;
vector<int> a[V * 2];

// int length[2];
int length[V * 2];

void generate() {
    queue<int> q;
    for (int i = 0; i < n * 2; i++) {
        if (d[i] == 0) {
            q.push(i);
        }
    }
    while (q.empty() == 0) {
        int u = q.front(), v = p[u];
        q.pop();
        f[u] = 1;
        d[v] = d[v] - 1;
        if (d[v] == 0) {
            q.push(v);
        }
    }
    for (int i = 0; i < n * 2; i++) {
        if (f[i] == 0) {
            vector<int> a;
            for (int u = i; f[u] == 0; u = p[u]) {
                a.push_back(u);
                f[u] = 1;
            }
            for (auto u : a) {
                length[u] = (int) a.size();
            }
        }
    }
}

bitset<V * 2> state;
int dist1[V * 2];
int dist2[V * 2];

void DFS1(int u) {
    state[u] = 1;
    for (auto v : a[u]) {
        if (state[v] == 0) {
            dist1[v] = dist1[u] + 1;
            DFS1(v);
        }
    }
}

void DFS2(int u) {
    state[u] = 1;
    for (auto v : a[u]) {
        if (state[v] == 0) {
            dist2[v] = dist2[u] + 1;
            DFS2(v);
        }
    }
}

int count1(int u, int k) {
    int sum = 0;
    for (int i = 0; i < n; i++) {
        if (length[u] == 0 && dist1[i] == k) {
            sum = sum + 1;
        }
        if (length[u] > 0 && k - dist1[i] >= 0 && (k - dist1[i]) % length[u] == 0) {
            sum = sum + 1;
        }
    }
    return sum;
}

int count2(int u, int k) {
    int sum = 0;
    for (int i = 0; i < n; i++) {
        if (length[u] == 0 && dist2[i] == k) {
            sum = sum + 1;
        }
        if (length[u] > 0 && k - dist2[i] >= 0 && (k - dist2[i]) % length[u] == 0) {
            sum = sum + 1;
        }
    }
    return sum;
}

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

    fill(t, t + n, m);
    for (int i = 0; i < m; i++) {
        int u, v;
        u = R[i][0];
        v = R[i][1];
        e[u].push_back({v, i});
        e[v].push_back({u, i});
        t[u] = min(t[u], i);
        t[v] = min(t[v], i);
    }

    for (int u = 0; u < n; u++) {
        int v, i;
        tie(v, i) = e[u][0];
        if (i != t[v]) {
            p[u] = v;
            d[v] = d[v] + 1;
            a[v].push_back(u);
        } else {
            p[u] = v + n;
            d[v + n] = d[v + n] + 1;
            a[v + n].push_back(u);
        }
        if ((int) e[u].size() > 1) {
            tie(v, i) = e[u][1];
        }
        if (i != t[v]) {
            p[u + n] = v;
            d[v] = d[v] + 1;
            a[v].push_back(u + n);
        } else {
            p[u + n] = v + n;
            d[v + n] = d[v + n] + 1;
            a[v + n].push_back(u + n);
        }
    }
    generate();

    state.reset();
    fill(dist1, dist1 + n * 2, (int) 1E9);
    dist1[x] = 0;
    DFS1(x);
    state.reset();
    fill(dist2, dist2 + n * 2, (int) 1E9);
    dist2[x + n] = 0;
    DFS2(x + n);

    int q = Q;

    for (int i = 0; i < q; i++) {
        int k = G[i];
        answer(count1(x, k) + count2(x + n, k));
        // cout << count(x, k) + count(x + n, k) << " ";
    }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11100 KB Output is correct
2 Correct 6 ms 11096 KB Output is correct
3 Correct 6 ms 11144 KB Output is correct
4 Correct 6 ms 11096 KB Output is correct
5 Correct 5 ms 11064 KB Output is correct
6 Correct 6 ms 11096 KB Output is correct
7 Correct 7 ms 11100 KB Output is correct
8 Correct 6 ms 11100 KB Output is correct
9 Correct 7 ms 11356 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11100 KB Output is correct
2 Correct 6 ms 11096 KB Output is correct
3 Correct 6 ms 11144 KB Output is correct
4 Correct 6 ms 11096 KB Output is correct
5 Correct 5 ms 11064 KB Output is correct
6 Correct 6 ms 11096 KB Output is correct
7 Correct 7 ms 11100 KB Output is correct
8 Correct 6 ms 11100 KB Output is correct
9 Correct 7 ms 11356 KB Output is correct
10 Correct 6 ms 11096 KB Output is correct
11 Correct 13 ms 14168 KB Output is correct
12 Correct 24 ms 16472 KB Output is correct
13 Correct 38 ms 28984 KB Output is correct
14 Correct 75 ms 28628 KB Output is correct
15 Correct 80 ms 29092 KB Output is correct
16 Correct 61 ms 24880 KB Output is correct
17 Correct 56 ms 23404 KB Output is correct
18 Correct 22 ms 16732 KB Output is correct
19 Correct 68 ms 28580 KB Output is correct
20 Correct 96 ms 29264 KB Output is correct
21 Correct 73 ms 24772 KB Output is correct
22 Correct 68 ms 23376 KB Output is correct
23 Correct 72 ms 30444 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11100 KB Output is correct
2 Correct 6 ms 11096 KB Output is correct
3 Correct 6 ms 11144 KB Output is correct
4 Correct 6 ms 11096 KB Output is correct
5 Correct 5 ms 11064 KB Output is correct
6 Correct 6 ms 11096 KB Output is correct
7 Correct 7 ms 11100 KB Output is correct
8 Correct 6 ms 11100 KB Output is correct
9 Correct 7 ms 11356 KB Output is correct
10 Correct 6 ms 11096 KB Output is correct
11 Correct 13 ms 14168 KB Output is correct
12 Correct 24 ms 16472 KB Output is correct
13 Correct 38 ms 28984 KB Output is correct
14 Correct 75 ms 28628 KB Output is correct
15 Correct 80 ms 29092 KB Output is correct
16 Correct 61 ms 24880 KB Output is correct
17 Correct 56 ms 23404 KB Output is correct
18 Correct 22 ms 16732 KB Output is correct
19 Correct 68 ms 28580 KB Output is correct
20 Correct 96 ms 29264 KB Output is correct
21 Correct 73 ms 24772 KB Output is correct
22 Correct 68 ms 23376 KB Output is correct
23 Correct 72 ms 30444 KB Output is correct
24 Correct 6 ms 11100 KB Output is correct
25 Correct 92 ms 14288 KB Output is correct
26 Correct 154 ms 16636 KB Output is correct
27 Correct 710 ms 29148 KB Output is correct
28 Correct 830 ms 28796 KB Output is correct
29 Correct 866 ms 29320 KB Output is correct
30 Correct 566 ms 24816 KB Output is correct
31 Correct 385 ms 23620 KB Output is correct
32 Correct 35 ms 16720 KB Output is correct
33 Correct 832 ms 28616 KB Output is correct
34 Correct 823 ms 29060 KB Output is correct
35 Correct 444 ms 24760 KB Output is correct
36 Correct 391 ms 23340 KB Output is correct
37 Correct 790 ms 30448 KB Output is correct
38 Correct 1978 ms 38708 KB Output is correct