oj.uz

Submission #1032195

# Submission time Handle Problem Language Result Execution time Memory
1032195 2024-07-23T13:02:53 Z VMaksimoski008 Tropical Garden (IOI11_garden) C++17
69 / 100
 5000 ms 68180 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];
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 3 ms 19036 KB Output is correct
2 Correct 4 ms 19036 KB Output is correct
3 Correct 4 ms 19036 KB Output is correct
4 Correct 3 ms 16732 KB Output is correct
5 Correct 3 ms 16840 KB Output is correct
6 Correct 3 ms 19032 KB Output is correct
7 Correct 2 ms 16836 KB Output is correct
8 Correct 3 ms 19036 KB Output is correct
9 Correct 4 ms 19032 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19036 KB Output is correct
2 Correct 4 ms 19036 KB Output is correct
3 Correct 4 ms 19036 KB Output is correct
4 Correct 3 ms 16732 KB Output is correct
5 Correct 3 ms 16840 KB Output is correct
6 Correct 3 ms 19032 KB Output is correct
7 Correct 2 ms 16836 KB Output is correct
8 Correct 3 ms 19036 KB Output is correct
9 Correct 4 ms 19032 KB Output is correct
10 Correct 2 ms 16732 KB Output is correct
11 Correct 15 ms 24348 KB Output is correct
12 Correct 28 ms 29540 KB Output is correct
13 Correct 52 ms 45404 KB Output is correct
14 Correct 100 ms 64260 KB Output is correct
15 Correct 99 ms 64848 KB Output is correct
16 Correct 72 ms 49868 KB Output is correct
17 Correct 66 ms 45020 KB Output is correct
18 Correct 25 ms 29532 KB Output is correct
19 Correct 95 ms 64336 KB Output is correct
20 Correct 112 ms 64964 KB Output is correct
21 Correct 74 ms 49748 KB Output is correct
22 Correct 62 ms 44884 KB Output is correct
23 Correct 115 ms 68180 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19036 KB Output is correct
2 Correct 4 ms 19036 KB Output is correct
3 Correct 4 ms 19036 KB Output is correct
4 Correct 3 ms 16732 KB Output is correct
5 Correct 3 ms 16840 KB Output is correct
6 Correct 3 ms 19032 KB Output is correct
7 Correct 2 ms 16836 KB Output is correct
8 Correct 3 ms 19036 KB Output is correct
9 Correct 4 ms 19032 KB Output is correct
10 Correct 2 ms 16732 KB Output is correct
11 Correct 15 ms 24348 KB Output is correct
12 Correct 28 ms 29540 KB Output is correct
13 Correct 52 ms 45404 KB Output is correct
14 Correct 100 ms 64260 KB Output is correct
15 Correct 99 ms 64848 KB Output is correct
16 Correct 72 ms 49868 KB Output is correct
17 Correct 66 ms 45020 KB Output is correct
18 Correct 25 ms 29532 KB Output is correct
19 Correct 95 ms 64336 KB Output is correct
20 Correct 112 ms 64964 KB Output is correct
21 Correct 74 ms 49748 KB Output is correct
22 Correct 62 ms 44884 KB Output is correct
23 Correct 115 ms 68180 KB Output is correct
24 Correct 6 ms 16732 KB Output is correct
25 Correct 1526 ms 24412 KB Output is correct
26 Correct 2907 ms 29544 KB Output is correct
27 Correct 4850 ms 45500 KB Output is correct
28 Execution timed out 5078 ms 66016 KB Time limit exceeded
29 Halted 0 ms 0 KB -