Submission #1032226

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032226		daoda	Tropical Garden (IOI11_garden)	C++17	100 / 100	1197 ms	49272 KiB

garden

#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 / 49
• Subtask 2: 20 / 20
• Subtask 3: 31 / 31