oj.uz

Submission #1081225

# Submission time Handle Problem Language Result Execution time Memory
1081225 2024-08-29T19:54:30 Z codexistent Tropical Garden (IOI11_garden) C++14
69 / 100
 5000 ms 77140 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
#define MAXN 150005
#define LOGN 31
#define FOR(i, a, b) for(int i = a; i <= b; i++)

int jmp[MAXN][LOGN][2], jmp2[MAXN][LOGN][2];
int ch[MAXN][2];

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
    FOR(i, 1, N) ch[i][0] = ch[i][1] = -1;
    FOR(i, 1, M){
        int x = R[i - 1][0] + 1, y = R[i - 1][1] + 1;
        if(ch[y][0] == -1){
            ch[y][0] = x;
        }else if(ch[y][1] == -1){
            ch[y][1] = x;
        }

        if(ch[x][0] == -1){
            ch[x][0] = y;
        }else if(ch[x][1] == -1){
            ch[x][1] = y;
        }
    }
    FOR(i, 1, N){
        jmp[i][0][0] = ch[i][0], jmp2[i][0][0] = i;
        if(ch[i][1] == -1){
            jmp[i][0][1] = -1;            
        }else{
            jmp[i][0][1] = ch[i][1], jmp2[i][0][1] = i;
        }
    }

    // jmp[node][jump size][next node] = 
    for(int j = 1; j <= LOGN - 1; j++){
        FOR(i, 1, N){
            // jmp[i][j][0]
            int hi = jmp[i][j - 1][0], h2i = jmp2[i][j - 1][0];
            if(ch[hi][0] != h2i || jmp[hi][j - 1][1] == -1){
                jmp[i][j][0] = jmp[hi][j - 1][0], jmp2[i][j][0] = jmp2[hi][j - 1][0];
            }else{
                jmp[i][j][0] = jmp[hi][j - 1][1], jmp2[i][j][0] = jmp2[hi][j - 1][1];
            }

            // jmp[i][j][1]
            if(jmp[i][j - 1][1] == -1){
                jmp[i][j][1] = -1;
                continue;
            }
            hi = jmp[i][j - 1][1], h2i = jmp2[i][j - 1][1];
            if(ch[hi][0] != h2i || jmp[hi][j - 1][1] == -1){
                jmp[i][j][1] = jmp[hi][j - 1][0], jmp2[i][j][1] = jmp2[hi][j - 1][0];
            }else{
                jmp[i][j][1] = jmp[hi][j - 1][1], jmp2[i][j][1] = jmp2[hi][j - 1][1];
            }
        }
    }

    P++;

    FOR(q, 1, Q){
        int r = 0, jd = G[q - 1];
        FOR(s, 1, N){
            int i = s, i2 = -1;
            FOR(j, 0, LOGN - 1){
                if((1 << j) & jd){
                    if(ch[i][0] != i2 || jmp[i][j][1] == -1){
                        i2 = jmp2[i][j][0], i = jmp[i][j][0];
                    }else{
                        i2 = jmp2[i][j][1], i = jmp[i][j][1];
                    }
                }
            }
            if(i == P) r++;
        }

        answer(r);
    } 
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 2 ms 972 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 2 ms 972 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 18 ms 11984 KB Output is correct
12 Correct 26 ms 19804 KB Output is correct
13 Correct 76 ms 43956 KB Output is correct
14 Correct 118 ms 69744 KB Output is correct
15 Correct 119 ms 70672 KB Output is correct
16 Correct 80 ms 48196 KB Output is correct
17 Correct 63 ms 40792 KB Output is correct
18 Correct 23 ms 19804 KB Output is correct
19 Correct 117 ms 69724 KB Output is correct
20 Correct 109 ms 70616 KB Output is correct
21 Correct 71 ms 48088 KB Output is correct
22 Correct 69 ms 40784 KB Output is correct
23 Correct 119 ms 77140 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 2 ms 972 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 18 ms 11984 KB Output is correct
12 Correct 26 ms 19804 KB Output is correct
13 Correct 76 ms 43956 KB Output is correct
14 Correct 118 ms 69744 KB Output is correct
15 Correct 119 ms 70672 KB Output is correct
16 Correct 80 ms 48196 KB Output is correct
17 Correct 63 ms 40792 KB Output is correct
18 Correct 23 ms 19804 KB Output is correct
19 Correct 117 ms 69724 KB Output is correct
20 Correct 109 ms 70616 KB Output is correct
21 Correct 71 ms 48088 KB Output is correct
22 Correct 69 ms 40784 KB Output is correct
23 Correct 119 ms 77140 KB Output is correct
24 Correct 8 ms 344 KB Output is correct
25 Correct 3941 ms 11992 KB Output is correct
26 Execution timed out 5038 ms 19800 KB Time limit exceeded
27 Halted 0 ms 0 KB -