oj.uz

Submission #1032194

# Submission time Handle Problem Language Result Execution time Memory
1032194 2024-07-23T13:02:04 Z VMaksimoski008 Tropical Garden (IOI11_garden) C++17
69 / 100
 5000 ms 69972 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

const int maxn = 3e5 + 5;

vector<int> graph_shit[maxn+5];
vector<int> graph[maxn+5];
int n, up[maxn][31];

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);
        else graph[i].push_back(v);
    }

    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);
            else graph[i].push_back(v);
        } else {
            int v = graph_shit[i-N][1];
            if(graph_shit[v][0] == i-N) graph[i].push_back(v+N);
            else graph[i].push_back(v);
        }
    }

    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];

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

        for(int j=0; j<N; j++) {
            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 4 ms 19032 KB Output is correct
2 Correct 3 ms 19036 KB Output is correct
3 Correct 3 ms 19032 KB Output is correct
4 Correct 4 ms 16732 KB Output is correct
5 Correct 3 ms 16832 KB Output is correct
6 Correct 5 ms 19172 KB Output is correct
7 Correct 4 ms 16732 KB Output is correct
8 Correct 4 ms 19036 KB Output is correct
9 Correct 5 ms 19336 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19032 KB Output is correct
2 Correct 3 ms 19036 KB Output is correct
3 Correct 3 ms 19032 KB Output is correct
4 Correct 4 ms 16732 KB Output is correct
5 Correct 3 ms 16832 KB Output is correct
6 Correct 5 ms 19172 KB Output is correct
7 Correct 4 ms 16732 KB Output is correct
8 Correct 4 ms 19036 KB Output is correct
9 Correct 5 ms 19336 KB Output is correct
10 Correct 3 ms 16728 KB Output is correct
11 Correct 19 ms 24668 KB Output is correct
12 Correct 33 ms 29908 KB Output is correct
13 Correct 62 ms 46484 KB Output is correct
14 Correct 111 ms 66132 KB Output is correct
15 Correct 145 ms 66656 KB Output is correct
16 Correct 87 ms 51508 KB Output is correct
17 Correct 70 ms 46568 KB Output is correct
18 Correct 37 ms 29992 KB Output is correct
19 Correct 115 ms 66128 KB Output is correct
20 Correct 106 ms 66648 KB Output is correct
21 Correct 73 ms 51280 KB Output is correct
22 Correct 75 ms 46416 KB Output is correct
23 Correct 123 ms 69972 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19032 KB Output is correct
2 Correct 3 ms 19036 KB Output is correct
3 Correct 3 ms 19032 KB Output is correct
4 Correct 4 ms 16732 KB Output is correct
5 Correct 3 ms 16832 KB Output is correct
6 Correct 5 ms 19172 KB Output is correct
7 Correct 4 ms 16732 KB Output is correct
8 Correct 4 ms 19036 KB Output is correct
9 Correct 5 ms 19336 KB Output is correct
10 Correct 3 ms 16728 KB Output is correct
11 Correct 19 ms 24668 KB Output is correct
12 Correct 33 ms 29908 KB Output is correct
13 Correct 62 ms 46484 KB Output is correct
14 Correct 111 ms 66132 KB Output is correct
15 Correct 145 ms 66656 KB Output is correct
16 Correct 87 ms 51508 KB Output is correct
17 Correct 70 ms 46568 KB Output is correct
18 Correct 37 ms 29992 KB Output is correct
19 Correct 115 ms 66128 KB Output is correct
20 Correct 106 ms 66648 KB Output is correct
21 Correct 73 ms 51280 KB Output is correct
22 Correct 75 ms 46416 KB Output is correct
23 Correct 123 ms 69972 KB Output is correct
24 Correct 8 ms 16728 KB Output is correct
25 Correct 2017 ms 24516 KB Output is correct
26 Correct 4115 ms 30032 KB Output is correct
27 Execution timed out 5064 ms 46396 KB Time limit exceeded
28 Halted 0 ms 0 KB -