oj.uz

Submission #1032880

# Submission time Handle Problem Language Result Execution time Memory
1032880 2024-07-24T10:20:53 Z VMaksimoski008 Tropical Garden (IOI11_garden) C++17
69 / 100
 5000 ms 105992 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]];
                for(int k=19; 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 10 ms 26712 KB Output is correct
2 Correct 9 ms 26716 KB Output is correct
3 Correct 9 ms 26820 KB Output is correct
4 Correct 9 ms 26316 KB Output is correct
5 Correct 9 ms 26380 KB Output is correct
6 Correct 11 ms 26968 KB Output is correct
7 Correct 9 ms 26204 KB Output is correct
8 Correct 9 ms 26716 KB Output is correct
9 Correct 11 ms 26972 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 26712 KB Output is correct
2 Correct 9 ms 26716 KB Output is correct
3 Correct 9 ms 26820 KB Output is correct
4 Correct 9 ms 26316 KB Output is correct
5 Correct 9 ms 26380 KB Output is correct
6 Correct 11 ms 26968 KB Output is correct
7 Correct 9 ms 26204 KB Output is correct
8 Correct 9 ms 26716 KB Output is correct
9 Correct 11 ms 26972 KB Output is correct
10 Correct 8 ms 26204 KB Output is correct
11 Correct 27 ms 37548 KB Output is correct
12 Correct 51 ms 46660 KB Output is correct
13 Correct 85 ms 76516 KB Output is correct
14 Correct 188 ms 99068 KB Output is correct
15 Correct 202 ms 100268 KB Output is correct
16 Correct 131 ms 76720 KB Output is correct
17 Correct 112 ms 69308 KB Output is correct
18 Correct 50 ms 46916 KB Output is correct
19 Correct 197 ms 99240 KB Output is correct
20 Correct 188 ms 100252 KB Output is correct
21 Correct 130 ms 76840 KB Output is correct
22 Correct 121 ms 69228 KB Output is correct
23 Correct 224 ms 105992 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 26712 KB Output is correct
2 Correct 9 ms 26716 KB Output is correct
3 Correct 9 ms 26820 KB Output is correct
4 Correct 9 ms 26316 KB Output is correct
5 Correct 9 ms 26380 KB Output is correct
6 Correct 11 ms 26968 KB Output is correct
7 Correct 9 ms 26204 KB Output is correct
8 Correct 9 ms 26716 KB Output is correct
9 Correct 11 ms 26972 KB Output is correct
10 Correct 8 ms 26204 KB Output is correct
11 Correct 27 ms 37548 KB Output is correct
12 Correct 51 ms 46660 KB Output is correct
13 Correct 85 ms 76516 KB Output is correct
14 Correct 188 ms 99068 KB Output is correct
15 Correct 202 ms 100268 KB Output is correct
16 Correct 131 ms 76720 KB Output is correct
17 Correct 112 ms 69308 KB Output is correct
18 Correct 50 ms 46916 KB Output is correct
19 Correct 197 ms 99240 KB Output is correct
20 Correct 188 ms 100252 KB Output is correct
21 Correct 130 ms 76840 KB Output is correct
22 Correct 121 ms 69228 KB Output is correct
23 Correct 224 ms 105992 KB Output is correct
24 Correct 11 ms 26204 KB Output is correct
25 Correct 967 ms 37456 KB Output is correct
26 Correct 1806 ms 46664 KB Output is correct
27 Correct 2818 ms 76768 KB Output is correct
28 Execution timed out 5039 ms 99244 KB Time limit exceeded
29 Halted 0 ms 0 KB -