Submission #1032897

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032897		VMaksimoski008	Tropical Garden (IOI11_garden)	C++17	100 / 100	2063 ms	108364 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,bmi,bmi2,lzcnt,popcnt")

const int maxn = 3e5 + 5;

vector<int> graph_shit[maxn+5], krug(maxn+5), id(maxn+5), SZ(maxn+5), bad(maxn+5), graph[maxn+5], vis(maxn+5), topo, rg[maxn+5];
vector<vector<int> > cmp;
int n, up[maxn][31], timer = 0, start;

void dfs(int u) {
    vis[u] = 1;
    for(int &v : graph[u])
        if(!vis[v]) dfs(v);
    topo.push_back(u);
}

void dfs2(int u) {
    cmp.back().push_back(u);
    vis[u] = 1;
    for(int &v : rg[u])
        if(!vis[v]) dfs2(v);
}

void dfs3(int u) {
    krug[u] = timer++;
    for(int &v : graph[u])
        if(v != start) dfs3(v);
}

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

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

    for(int i=0; i<N; i++) {
        int v = graph_shit[i][0];
        if(graph_shit[v][0] == i) {
            graph[i].push_back(v+N);
            rg[v+N].push_back(i);
        } else {
            graph[i].push_back(v);
            rg[v].push_back(i);
        }
    }

    for(int i=N; i<2*N; i++) {
        if(graph_shit[i-N].size() == 1) {
            int v = graph_shit[i-N][0];
            if(graph_shit[v][0] == i-N) {
                graph[i].push_back(v+N);
                rg[v+N].push_back(i);
            } else {
                graph[i].push_back(v);
                rg[v].push_back(i);
            }
        } else {
            int v = graph_shit[i-N][1];
            if(graph_shit[v][0] == i-N) {
                graph[i].push_back(v+N);
                rg[v+N].push_back(i);
            } else {
                graph[i].push_back(v);
                rg[v].push_back(i);
            }
        }
    }

    for(int i=0; i<2*N; i++) if(!vis[i]) dfs(i);
    for(int i=0; i<2*N; i++) vis[i] = 0;
    reverse(topo.begin(), topo.end());

    int koce = 1;
    for(int &i : topo) {
        if(vis[i]) continue;
        cmp.push_back({ });
        dfs2(i);
        for(int &x : cmp.back()) id[x] = koce;
        SZ[koce] = cmp.back().size();
        if(cmp.back().size() >= 2) {
            for(int &x : cmp.back()) bad[x] = 1;
            timer = 0; start = cmp.back().at(0);
            dfs3(cmp.back().at(0));
        }
        koce++;
    }

    for(int i=0; i<2*N; i++) up[i][0] = graph[i].back();

    for(int j=1; j<31; j++)
        for(int i=0; i<2*N; i++) up[i][j] = up[up[i][j-1]][j-1];

    vector<ll> to_cycle(2*N, -1), cycle_id(2*N);

    for(int i=0; i<2*N; i++) {
        int curr = i;
        ll dist = 0;
        for(int j=30; j>=0; j--) {
            if(!bad[up[curr][j]]) {
                dist += (1ll << j);
                curr = up[curr][j];
            }
        }

        if(bad[up[curr][0]]) {
            if(bad[i]) to_cycle[i] = 0;
            else to_cycle[i] = dist + 1;
            if(bad[i]) cycle_id[i] = i;
            else cycle_id[i] = up[curr][0];
        }
    }

    for(int i=0; i<Q; i++) {
        int ans=0;

        for(int j=0; j<N; j++) {
            if(to_cycle[j] != -1 && to_cycle[j] <= G[i]) {
                int curr = cycle_id[j];
                int K = (G[i] - to_cycle[j]) % SZ[id[curr]];
                if(id[P] != id[curr] && id[P+N] != id[curr]) continue;
                // for(int k=20; k>=0; k--)
                //     if(K & (1ll << k)) curr = up[curr][k];
                // if(curr == P || curr == P + N) ans++;
                if(id[P] == id[curr]) {
                    if(krug[curr] <= krug[P] && krug[P] - krug[curr] == K) ans++; 
                    if(krug[curr] > krug[P] && SZ[id[curr]] - krug[curr] + krug[P] == K) ans++;
                }

                if(id[P+N] == id[curr]) {
                    if(krug[curr] <= krug[P+N] && krug[P+N] - krug[curr] == K) ans++; 
                    if(krug[curr] > krug[P+N] && SZ[id[curr]] - krug[curr] + krug[P+N] == K) ans++;
                }
            } else if(to_cycle[j] == -1 || to_cycle[j] > G[i]) {
                int curr = j;
                for(int k=30; k>=0; k--)
                    if(G[i] & (1ll << k)) curr = up[curr][k];
                if(curr == P || curr == P + N) ans++;
            }
        }

        answer(ans);
    }
}

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