oj.uz

Submission #598128

# Submission time Handle Problem Language Result Execution time Memory
598128 2022-07-17T16:50:01 Z snasibov05 Tropical Garden (IOI11_garden) C++14
69 / 100
 262 ms 77228 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>

using namespace std;


void count_routes(int n, int m, int p, int r[][2], int q, int g[]){
    const int lg = 32;

    vector<vector<int>> ed(n, vector<int>(2, -1));
    for (int i = 0; i < m; ++i) {
        if (ed[r[i][0]][0] == -1) ed[r[i][0]][0] = r[i][1];
        else if (ed[r[i][0]][1] == -1) ed[r[i][0]][1] = r[i][1];

        if (ed[r[i][1]][0] == -1) ed[r[i][1]][0] = r[i][0];
        else if (ed[r[i][1]][1] == -1) ed[r[i][1]][1] = r[i][0];
    }

    for (int i = 0; i < n; ++i) {
        if (ed[i][1] == -1) ed[i][1] = ed[i][0];
    }

    vector<vector<int>> gg(2*n);
    for (int i = 0; i < n; ++i){
        int t1 = ed[i][0];
        if (ed[t1][0] == i) gg[i].push_back(t1 + n);
        else gg[i].push_back(t1);

        int t2 = ed[i][1];
        if (ed[t2][0] == i) gg[i + n].push_back(t2 + n);
        else gg[i + n].push_back(t2);
    }


    vector<vector<int>> up(2*n, vector<int>(lg));
    for (int i = 0; i < 2*n; ++i) up[i][0] = gg[i][0];
    for (int i = 1; i < lg; ++i){
        for (int j = 0; j < 2*n; ++j){
            up[j][i] = up[up[j][i-1]][i-1];
        }
    }

    int ans = 0;
    for (int i = 0; i < n; ++i){
        int cur = i;
        int k = g[0];
        int x = 0;
        while (k > 0){
            if (k % 2) cur = up[cur][x];
            x++; k /= 2;
        }
        if (cur == p || cur == p + n) ans++;
    }

    answer(ans);
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 700 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 2 ms 896 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 700 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 2 ms 896 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 26 ms 11700 KB Output is correct
12 Correct 52 ms 19788 KB Output is correct
13 Correct 147 ms 43976 KB Output is correct
14 Correct 226 ms 69592 KB Output is correct
15 Correct 221 ms 70532 KB Output is correct
16 Correct 169 ms 48056 KB Output is correct
17 Correct 126 ms 40652 KB Output is correct
18 Correct 49 ms 19828 KB Output is correct
19 Correct 223 ms 69708 KB Output is correct
20 Correct 225 ms 70528 KB Output is correct
21 Correct 156 ms 48056 KB Output is correct
22 Correct 119 ms 40652 KB Output is correct
23 Correct 262 ms 77228 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 700 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 2 ms 896 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 26 ms 11700 KB Output is correct
12 Correct 52 ms 19788 KB Output is correct
13 Correct 147 ms 43976 KB Output is correct
14 Correct 226 ms 69592 KB Output is correct
15 Correct 221 ms 70532 KB Output is correct
16 Correct 169 ms 48056 KB Output is correct
17 Correct 126 ms 40652 KB Output is correct
18 Correct 49 ms 19828 KB Output is correct
19 Correct 223 ms 69708 KB Output is correct
20 Correct 225 ms 70528 KB Output is correct
21 Correct 156 ms 48056 KB Output is correct
22 Correct 119 ms 40652 KB Output is correct
23 Correct 262 ms 77228 KB Output is correct
24 Incorrect 1 ms 340 KB Output isn't correct
25 Halted 0 ms 0 KB -