oj.uz

Submission #1032887

# Submission time Handle Problem Language Result Execution time Memory
1032887 2024-07-24T10:24:52 Z VMaksimoski008 Tropical Garden (IOI11_garden) C++17
69 / 100
 5000 ms 106376 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], 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];

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 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;
        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++;
            } 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 8 ms 27996 KB Output is correct
2 Correct 8 ms 28252 KB Output is correct
3 Correct 9 ms 28256 KB Output is correct
4 Correct 6 ms 27596 KB Output is correct
5 Correct 7 ms 27484 KB Output is correct
6 Correct 9 ms 28252 KB Output is correct
7 Correct 8 ms 27736 KB Output is correct
8 Correct 7 ms 28252 KB Output is correct
9 Correct 9 ms 28352 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 27996 KB Output is correct
2 Correct 8 ms 28252 KB Output is correct
3 Correct 9 ms 28256 KB Output is correct
4 Correct 6 ms 27596 KB Output is correct
5 Correct 7 ms 27484 KB Output is correct
6 Correct 9 ms 28252 KB Output is correct
7 Correct 8 ms 27736 KB Output is correct
8 Correct 7 ms 28252 KB Output is correct
9 Correct 9 ms 28352 KB Output is correct
10 Correct 7 ms 27736 KB Output is correct
11 Correct 29 ms 38992 KB Output is correct
12 Correct 55 ms 47996 KB Output is correct
13 Correct 80 ms 77960 KB Output is correct
14 Correct 189 ms 100528 KB Output is correct
15 Correct 208 ms 101408 KB Output is correct
16 Correct 136 ms 78116 KB Output is correct
17 Correct 114 ms 70408 KB Output is correct
18 Correct 51 ms 48200 KB Output is correct
19 Correct 190 ms 100608 KB Output is correct
20 Correct 205 ms 101552 KB Output is correct
21 Correct 135 ms 78264 KB Output is correct
22 Correct 124 ms 70580 KB Output is correct
23 Correct 246 ms 106376 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 27996 KB Output is correct
2 Correct 8 ms 28252 KB Output is correct
3 Correct 9 ms 28256 KB Output is correct
4 Correct 6 ms 27596 KB Output is correct
5 Correct 7 ms 27484 KB Output is correct
6 Correct 9 ms 28252 KB Output is correct
7 Correct 8 ms 27736 KB Output is correct
8 Correct 7 ms 28252 KB Output is correct
9 Correct 9 ms 28352 KB Output is correct
10 Correct 7 ms 27736 KB Output is correct
11 Correct 29 ms 38992 KB Output is correct
12 Correct 55 ms 47996 KB Output is correct
13 Correct 80 ms 77960 KB Output is correct
14 Correct 189 ms 100528 KB Output is correct
15 Correct 208 ms 101408 KB Output is correct
16 Correct 136 ms 78116 KB Output is correct
17 Correct 114 ms 70408 KB Output is correct
18 Correct 51 ms 48200 KB Output is correct
19 Correct 190 ms 100608 KB Output is correct
20 Correct 205 ms 101552 KB Output is correct
21 Correct 135 ms 78264 KB Output is correct
22 Correct 124 ms 70580 KB Output is correct
23 Correct 246 ms 106376 KB Output is correct
24 Correct 8 ms 27740 KB Output is correct
25 Correct 169 ms 38788 KB Output is correct
26 Correct 185 ms 47948 KB Output is correct
27 Correct 3162 ms 78112 KB Output is correct
28 Correct 1867 ms 100520 KB Output is correct
29 Execution timed out 5046 ms 101556 KB Time limit exceeded
30 Halted 0 ms 0 KB -