oj.uz

Submission #1032897

# Submission time Handle Problem Language Result Execution time Memory
1032897 2024-07-24T10:32:03 Z VMaksimoski008 Tropical Garden (IOI11_garden) C++17
100 / 100
 2063 ms 108364 KB 
#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.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 27736 KB Output is correct
2 Correct 12 ms 27968 KB Output is correct
3 Correct 12 ms 27996 KB Output is correct
4 Correct 11 ms 27376 KB Output is correct
5 Correct 11 ms 27480 KB Output is correct
6 Correct 12 ms 27996 KB Output is correct
7 Correct 11 ms 27476 KB Output is correct
8 Correct 13 ms 28016 KB Output is correct
9 Correct 16 ms 27996 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 27736 KB Output is correct
2 Correct 12 ms 27968 KB Output is correct
3 Correct 12 ms 27996 KB Output is correct
4 Correct 11 ms 27376 KB Output is correct
5 Correct 11 ms 27480 KB Output is correct
6 Correct 12 ms 27996 KB Output is correct
7 Correct 11 ms 27476 KB Output is correct
8 Correct 13 ms 28016 KB Output is correct
9 Correct 16 ms 27996 KB Output is correct
10 Correct 11 ms 27484 KB Output is correct
11 Correct 30 ms 38696 KB Output is correct
12 Correct 54 ms 47776 KB Output is correct
13 Correct 84 ms 77904 KB Output is correct
14 Correct 196 ms 100092 KB Output is correct
15 Correct 190 ms 101036 KB Output is correct
16 Correct 179 ms 78040 KB Output is correct
17 Correct 117 ms 70452 KB Output is correct
18 Correct 71 ms 48048 KB Output is correct
19 Correct 192 ms 100272 KB Output is correct
20 Correct 206 ms 101096 KB Output is correct
21 Correct 176 ms 78252 KB Output is correct
22 Correct 117 ms 70372 KB Output is correct
23 Correct 230 ms 107156 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 27736 KB Output is correct
2 Correct 12 ms 27968 KB Output is correct
3 Correct 12 ms 27996 KB Output is correct
4 Correct 11 ms 27376 KB Output is correct
5 Correct 11 ms 27480 KB Output is correct
6 Correct 12 ms 27996 KB Output is correct
7 Correct 11 ms 27476 KB Output is correct
8 Correct 13 ms 28016 KB Output is correct
9 Correct 16 ms 27996 KB Output is correct
10 Correct 11 ms 27484 KB Output is correct
11 Correct 30 ms 38696 KB Output is correct
12 Correct 54 ms 47776 KB Output is correct
13 Correct 84 ms 77904 KB Output is correct
14 Correct 196 ms 100092 KB Output is correct
15 Correct 190 ms 101036 KB Output is correct
16 Correct 179 ms 78040 KB Output is correct
17 Correct 117 ms 70452 KB Output is correct
18 Correct 71 ms 48048 KB Output is correct
19 Correct 192 ms 100272 KB Output is correct
20 Correct 206 ms 101096 KB Output is correct
21 Correct 176 ms 78252 KB Output is correct
22 Correct 117 ms 70372 KB Output is correct
23 Correct 230 ms 107156 KB Output is correct
24 Correct 13 ms 27484 KB Output is correct
25 Correct 156 ms 38656 KB Output is correct
26 Correct 249 ms 47692 KB Output is correct
27 Correct 770 ms 77900 KB Output is correct
28 Correct 1227 ms 100184 KB Output is correct
29 Correct 1356 ms 101048 KB Output is correct
30 Correct 685 ms 78016 KB Output is correct
31 Correct 761 ms 70496 KB Output is correct
32 Correct 225 ms 47952 KB Output is correct
33 Correct 1241 ms 100348 KB Output is correct
34 Correct 1285 ms 101288 KB Output is correct
35 Correct 821 ms 78164 KB Output is correct
36 Correct 709 ms 70336 KB Output is correct
37 Correct 1161 ms 107180 KB Output is correct
38 Correct 2063 ms 108364 KB Output is correct