oj.uz

Submission #1032226

# Submission time Handle Problem Language Result Execution time Memory
1032226 2024-07-23T13:36:35 Z daoda Tropical Garden (IOI11_garden) C++17
100 / 100
 1197 ms 49272 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>

#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define FOR(x, a, b) for(ll x=a;x < ll(b); x++)
#define endl '\n'
#define TESTCASE ll t; cin >> t; for(ll T=0; T < t; T++)

using namespace std;
// using namespace __gnu_pbds;

typedef unsigned long long int ull;
typedef long long int ll;
typedef vector<ll> vll;
typedef pair<ll,ll> pll;
typedef vector<pll> vpll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
typedef vector<short> vs;
typedef long double ld;

// template <class T>
// using Tree = 
    // tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const ll INF = ll(1e9) + 10;
const ll INIT = 7;
const ll MAX_VAL = 50;
const ll MAX_SZ = (ll) 1e4;
const ll MAX_N = 150000;
const ll MAX_M = MAX_N;
const long double eps = 1e-4;
const ll MOD = ll(1e9) + 7;

vi rd = {0, 1, 0, -1}, cd = {1, 0, -1, 0};

ll add(ll a, ll b) {
    return ((a % MOD) + (b % MOD) + 2ll * MOD) % MOD;
}

ll mult(ll a, ll b) {
    return (((a % MOD) * (b % MOD)) + MOD) % MOD;
}

ll lcm(ll a, ll b) {
    return (a * b) / gcd(a, b);
}

struct Info {
    int cycle_sz = -1;
    vi incycle, outcycle;
};

int n, m, p, q;
int* g;
int (*r)[2];

int best[MAX_N][2];

// [0, n) is assuming that we go to the most beautiful next, other is sec most

int graph[2*MAX_N], visited[2*MAX_N];
Info info[2*MAX_N];

vi p_locs;
int cycle_strt = -1, cycle_end = -1;

void dfs(int node, int iter) {
    // cout << node << " ";

    if(visited[node]) {
        if(info[node].cycle_sz == -1) {
            cycle_strt = visited[node];
            cycle_end = iter - 1;
        }

        // cout << endl;
        // cout << cycle_strt << " " << cycle_end << endl;

        return;
    }

    visited[node] = iter;
    if(node % n == p) p_locs.push_back(iter);

    dfs(graph[node], iter + 1);

    if(cycle_strt != -1 && iter >= cycle_strt) {
        info[node].cycle_sz = cycle_end - cycle_strt + 1;
            
        for(auto p_id : p_locs) {
            if(p_id >= cycle_strt) {
                info[node].incycle.push_back((p_id - visited[node] + info[node].cycle_sz) % info[node].cycle_sz);
            }
        }
    } else {
        for(auto loc : p_locs) if(iter == loc) info[node].outcycle.push_back(0);
        for(auto dist : info[graph[node]].incycle) info[node].incycle.push_back(dist + 1);
        for(auto dist : info[graph[node]].outcycle) info[node].outcycle.push_back(dist + 1);

        info[node].cycle_sz = info[graph[node]].cycle_sz;
    }
}

bool check(int route_len, int strt) {
    for(auto dist : info[strt].outcycle) {
        if(route_len == dist) return true;
    }

    for(auto dist : info[strt].incycle) {
        if(route_len >= dist && (route_len - dist) % info[strt].cycle_sz == 0) return true; 
    }

    return false;
}

void count_routes(int i1, int i2, int i3, int i4[][2], int i5, int* i6) {
    n = i1; m = i2; p = i3; r = i4; q = i5; g = i6;

    for(auto &x : best) for(auto& y : x) y = -1;

    FOR(i, 0, m) {
        FOR(j, 0, 2) {
            if(best[r[i][j]][0] == -1) best[r[i][j]][0] = r[i][!j];
            else if(best[r[i][j]][1] == -1) best[r[i][j]][1] = r[i][!j];
        }
    }

    FOR(i, 0, n) if(best[i][1] == -1) best[i][1] = best[i][0];
    FOR(i, 0, n) {
        graph[i] = best[i][0];
        if(i == best[best[i][0]][0]) graph[i] += n;
    }
    FOR(i, n, (n << 1)) {
        graph[i] = best[i - n][1];
        if(i - n == best[best[i - n][1]][0]) graph[i] += n;
    }

    // FOR(i, 0, n) cout << best[i][0] << " " << best[i][1] << endl;

    // FOR(i, 0, 2*n) cout << graph[i] << " ";
    // cout << endl;

    FOR(i, 0, n) {
        // cout << i << " : ";
        dfs(i, 1);
        // cout << endl;

        p_locs.clear();
        cycle_strt = cycle_end = -1;
    }

    FOR(i, 0, q) {
        int ans = 0;

        // FOR(j, 0, n) {
        //     cout << "node : " << j << endl;
        //     cout << "next : " << graph[j] << endl;
        //     cout << "cycle size : " << info[j].cycle_sz << endl; 
        //     cout << "p inside cycle : ";
        //     for(auto x : info[j].incycle) cout << x << " ";
        //     cout << endl;
        //     cout << "p outside cycle : ";
        //     for(auto x : info[j].outcycle) cout << x << " ";
        //     cout << endl << endl;
        // }

        FOR(j, 0, n) {
            ans += check(g[i], j);
        }

        // cout << ans << endl;
        answer(ans);
    }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 18780 KB Output is correct
2 Correct 3 ms 18940 KB Output is correct
3 Correct 3 ms 18780 KB Output is correct
4 Correct 3 ms 18852 KB Output is correct
5 Correct 3 ms 18780 KB Output is correct
6 Correct 4 ms 18780 KB Output is correct
7 Correct 3 ms 18780 KB Output is correct
8 Correct 3 ms 18780 KB Output is correct
9 Correct 4 ms 19036 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 18780 KB Output is correct
2 Correct 3 ms 18940 KB Output is correct
3 Correct 3 ms 18780 KB Output is correct
4 Correct 3 ms 18852 KB Output is correct
5 Correct 3 ms 18780 KB Output is correct
6 Correct 4 ms 18780 KB Output is correct
7 Correct 3 ms 18780 KB Output is correct
8 Correct 3 ms 18780 KB Output is correct
9 Correct 4 ms 19036 KB Output is correct
10 Correct 3 ms 18780 KB Output is correct
11 Correct 7 ms 20060 KB Output is correct
12 Correct 10 ms 20316 KB Output is correct
13 Correct 35 ms 45092 KB Output is correct
14 Correct 24 ms 23292 KB Output is correct
15 Correct 32 ms 26972 KB Output is correct
16 Correct 26 ms 25180 KB Output is correct
17 Correct 25 ms 24056 KB Output is correct
18 Correct 11 ms 20056 KB Output is correct
19 Correct 26 ms 23632 KB Output is correct
20 Correct 32 ms 27484 KB Output is correct
21 Correct 29 ms 25684 KB Output is correct
22 Correct 28 ms 25020 KB Output is correct
23 Correct 26 ms 23644 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 18780 KB Output is correct
2 Correct 3 ms 18940 KB Output is correct
3 Correct 3 ms 18780 KB Output is correct
4 Correct 3 ms 18852 KB Output is correct
5 Correct 3 ms 18780 KB Output is correct
6 Correct 4 ms 18780 KB Output is correct
7 Correct 3 ms 18780 KB Output is correct
8 Correct 3 ms 18780 KB Output is correct
9 Correct 4 ms 19036 KB Output is correct
10 Correct 3 ms 18780 KB Output is correct
11 Correct 7 ms 20060 KB Output is correct
12 Correct 10 ms 20316 KB Output is correct
13 Correct 35 ms 45092 KB Output is correct
14 Correct 24 ms 23292 KB Output is correct
15 Correct 32 ms 26972 KB Output is correct
16 Correct 26 ms 25180 KB Output is correct
17 Correct 25 ms 24056 KB Output is correct
18 Correct 11 ms 20056 KB Output is correct
19 Correct 26 ms 23632 KB Output is correct
20 Correct 32 ms 27484 KB Output is correct
21 Correct 29 ms 25684 KB Output is correct
22 Correct 28 ms 25020 KB Output is correct
23 Correct 26 ms 23644 KB Output is correct
24 Correct 4 ms 18780 KB Output is correct
25 Correct 134 ms 20068 KB Output is correct
26 Correct 221 ms 20316 KB Output is correct
27 Correct 732 ms 45136 KB Output is correct
28 Correct 1171 ms 23328 KB Output is correct
29 Correct 1095 ms 26984 KB Output is correct
30 Correct 666 ms 25208 KB Output is correct
31 Correct 695 ms 24404 KB Output is correct
32 Correct 231 ms 20060 KB Output is correct
33 Correct 1142 ms 23864 KB Output is correct
34 Correct 1117 ms 27572 KB Output is correct
35 Correct 736 ms 25828 KB Output is correct
36 Correct 1197 ms 26368 KB Output is correct
37 Correct 964 ms 23636 KB Output is correct
38 Correct 1065 ms 49272 KB Output is correct