Submission #1126217

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126217		fonikos01	Tropical Garden (IOI11_garden)	C++20	0 / 100	4 ms	5184 KiB

garden

#include <bits/stdc++.h>
#include <vector>
#include <tuple>
#include "garden.h"
#include "gardenlib.h"
// #include "debugging.h"
// #include <atcoder/lazysegtree>
// #include <atcoder/dsu>

// #include <atcoder/segtree>
// #include <atcoder/modint>
// using namespace atcoder;
// using mint = static_modint<998244353>;

using namespace std;
const int LARGE = 1e9;

#define all(x) (x).begin(), (x).end()

using ll = long long;
typedef pair<ll, ll> pi;
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
struct chash
{                                                   /// use most bits rather than just the lowest ones
        const uint64_t C = ll(4e18 * acos(0)) + 71; // large odd number
        const int RANDOM = rng();
        ll operator()(ll x) const { return __builtin_bswap64((x ^ RANDOM) * C); }
}; /// https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html
/// template<class K,class V> using um = unordered_map<K,V,chash>;
template <class K, class V>
using ht = gp_hash_table<K, V, chash, equal_to<K>, direct_mask_range_hashing<>,
                         linear_probe_fn<>,
                         hash_standard_resize_policy<hash_exponential_size_policy<>,
                                                     hash_load_check_resize_trigger<>, true>>;
template <class K, class V>
V get(ht<K, V> &u, K x)
{
        auto it = u.find(x);
        return it == end(u) ? 0 : it->s;
}

// bool cmp(pair<ll, ll> a, pair<ll, ll> b)
// {
//         if (a.second < b.second)
//                 return true;
//         return false;
// }
// struct node
// {
//         // part which will store data
//         int data;
//         // pointer to the previous node
//         struct node *prev;
//         // pointer to the next node
//         struct node *next;
// };
// struct trienode
// {
//         vector<trienode*> desc;
//         vector<ll> descExist;

//         trienode(ll M) {
//                 desc.resize(M);
//                 descExist.resize(M);
//         }
// };
const int MOD = 998244353;
// template<int MOD, int RT> struct mint {
// 	static const int mod = MOD;
// 	static constexpr mint rt() { return RT; } // primitive root
//  	int v;
//  	explicit operator int() const { return v; }
// 	mint():v(0) {}
// 	mint(ll _v):v(int(_v%MOD)) { v += (v<0)*MOD; }
// 	mint& operator+=(mint o) {
// 		if ((v += o.v) >= MOD) v -= MOD;
// 		return *this; }
// 	mint& operator-=(mint o) {
// 		if ((v -= o.v) < 0) v += MOD;
// 		return *this; }
// 	mint& operator*=(mint o) {
// 		v = int((ll)v*o.v%MOD); return *this; }
// 	friend mint pow(mint a, ll p) { assert(p >= 0);
// 		return p==0?1:pow(a*a,p/2)*(p&1?a:1); }
// 	friend mint inv(mint a) { assert(a.v != 0); return pow(a,MOD-2); }
// 	friend mint operator+(mint a, mint b) { return a += b; }
// 	friend mint operator-(mint a, mint b) { return a -= b; }
// 	friend mint operator*(mint a, mint b) { return a *= b; }
// };
// using mi = mint<(int)MOD, 5>;

// struct mySeg
// {
//         vector<ll> A;
//         ll N;

//         void build()
//         {
//                 A.resize(N * 2);
//                 for (int i = 0; i < N; i++)
//                         A[i + N] = A[i];
//                 for (int i = N - 1; i > 0; i--)
//                         A[i] = min(A[i << 1], A[i << 1 ^ 1]);
//                 // for (auto el : A) cout << el << " ";
//         }

//         void set(ll idx, ll val)
//         {
//                 idx += N;
//                 A[idx] = val;
//                 for (int i = idx >> 1; i > 0; i >>= 1)
//                         A[i] = min(A[i << 1], A[i << 1 ^ 1]);
//                 // for (auto el : A) cout << el << " ";
//         }

//         ll minnQuery(ll l, ll r)
//         {
//                 ll minn = INT64_MAX;
//                 for (l = l + N, r = r + N; l < r; l >>= 1, r >>= 1)
//                 {
//                         if (l % 2)
//                                 minn = min(minn, A[l++]);
//                         if (r % 2)
//                                 minn = min(minn, A[--r]);
//                 }
//                 return minn;
//         }
// };

// template <class T>
// class myFen
// {
// private:
//         int N;
//         vector<T> A;
//         vector<T> BIT;

// public:
//         myFen(int size) : N(size), A(size + 1), BIT(size + 1) {}

//         void set(ll idx, ll val)
//         {
//                 update(idx, val - A[idx]);
//                 A[idx] = val;
//         }
//         void update(ll idx, ll diff)
//         {
//                 for (idx = idx; idx <= N; idx += idx & (-idx))
//                         BIT[idx] += diff;
//         }
//         ll sumQuery(ll idx)
//         {
//                 if (idx == 0)
//                         return 0LL;
//                 ll summ = 0;
//                 for (idx = idx; idx > 0; idx -= idx & (-idx))
//                         summ += BIT[idx];
//                 return summ;
//         }
// };

// mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

// class HashedString {
//   private:
// 	// change M and B if you want
// 	static const ll M = (1LL << 61) - 1;
// 	static const ll B;

// 	// pow[i] contains B^i % M
// 	static vector<ll> pow;

// 	// p_hash[i] is the hash of the first i characters of the given string
// 	vector<ll> p_hash;

// 	__int128 mul(ll a, ll b) { return (__int128)a * b; }
// 	ll mod_mul(ll a, ll b) { return mul(a, b) % M; }

//   public:
// 	HashedString(const string &s) : p_hash(s.size() + 1) {
// 		while (pow.size() < s.size()) { pow.push_back(mod_mul(pow.back(), B)); }
// 		p_hash[0] = 0;
// 		for (int i = 0; i < s.size(); i++) {
// 			p_hash[i + 1] = (mul(p_hash[i], B) + s[i]) % M;
// 		}
// 	}

// 	ll get_hash(int start, int end) {
// 		ll raw_val = p_hash[end + 1] - mod_mul(p_hash[start], pow[end - start + 1]);
// 		return (raw_val + M) % M;
// 	}
// };
// vector<ll> HashedString::pow = {1};
// const ll HashedString::B = uniform_int_distribution<ll>(0, M - 1)(rng);
ll power(ll x, ll y, ll M)
{
        if (y == 0)
                return ll(1);

        ll p = power(x, y / ll(2), M) % M;
        p = (p * p) % M;

        return (y % ll(2) == 0) ? p : (x * p) % M;
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
        vector<ll> ans(Q);
        vector<vector<ll>> g(N, vector<ll>(0));
        for (int i = 0; i < M; i++) {
                g[R[i][0]].push_back(R[i][1]);
                g[R[i][1]].push_back(R[i][0]);
        }

        vector<ll> nodesComponent(N, -1);
        vector<vector<ll>> DP(N, vector<ll>(2, -1));

        ll timer = -1;
        ll cycSz = -1;
        auto dfs = [&](auto self, ll node, ll prevNode) -> void {
                timer++;
                ll state = 0, nextNode = g[node][0];
                if (g[node][0] == prevNode && g[node].size() >= 2) {
                        state = 1;
                        nextNode = g[node][1];
                }
                if (DP[node][state] != -1) {
                        if (node == P) cycSz = DP[node][state]-timer;
                        return ;
                }
                DP[node][state] = timer;
                self(self, nextNode, node);
                return ;
        };

        dfs(dfs, P, -1);

        DP.clear();
        DP.resize(N, vector<ll>(2, -2));

        auto prop = [&](auto self, ll node, ll prevNode) -> ll {
                ll state = 0, nextNode = g[node][0];
                if (g[node][0] == prevNode && g[node].size() >= 2) {
                        state = 1;
                        nextNode = g[node][1];
                }
                if (DP[node][state] != -2) {
                        return DP[node][state];
                }
                DP[node][state] = -1;
                DP[node][state] = self(self, nextNode, node);
                return DP[node][state];
        };

        for (int i = 0; i < N; i++) {
                prop(prop, i, -1);
        }

        vector<pair<ll,ll>> bfs = {{P, -1}};
        vector<set<ll>> fromNeiVis(N);
        fromNeiVis[P].insert(-1);
        ll step = 0, round = 0;
        vector<vector<ll>> psVals(2e5, vector<ll>(0));
        while (!bfs.empty()) {
                vector<pair<ll,ll>> newbfs(0);
                
                for (auto [node, prevNode] : bfs) {
                        ll state = 1;
                        if (g[node][0] == prevNode || prevNode == -1) {
                                state = 0;
                        }

                        if (state == 0) {
                                if (psVals[step].size() == round) {
                                        psVals[step].push_back(0);
                                        if (round > 0) psVals[step][round] += psVals[step][round-1];
                                }
                                psVals[step][round]++;
                        }
                        for (auto nei : g[node]) {
                                if (fromNeiVis[nei].count(node)) continue;
                                fromNeiVis[nei].insert(node);
                                newbfs.push_back(make_pair(nei, node));
                        }
                }
                step++;
                if (step == cycSz) {
                        step = 0;
                        round++;
                }
                bfs = newbfs;
        }

        for (int i = 0; i < Q; i++) {
                if (cycSz == -1 && G[i] < 2e5) ans[i] = psVals[G[i]][0];
                else if (cycSz != -1) {
                        ll dCnt = G[i]/cycSz;
                        ll rem = G[i]%cycSz;
                        dCnt = min(dCnt, ll(psVals[rem].size())-1LL);
                        ans[i] = psVals[rem][dCnt];
                }
                answer(ans[i]);
        }
        
        return ;
}

// void count_routes(ll N, ll M, ll P, vector<vector<ll>> R, ll Q, vector<ll> G)
// {
//         ios::sync_with_stdio(false);
//         cin.tie(nullptr);
//         // freopen("cruise.in", "r", stdin);
//         // freopen("cruise.out", "w", stdout);

//         // ll caseCnt = 1;

//         // ll T;
//         // cin >> T;
//         // while (T--)
//         // {

//         solve(N,M,P,R,Q,G);

//         // 	cout << "Case #"<< caseCnt << ": " << ans << '\n';
//         // 	caseCnt++;
//         // }

//         return ;
// }

• Subtask 1: 0 / 49
• Subtask 2: 0 / 20
• Subtask 3: 0 / 31