oj.uz

Submission #103457

# Submission time Handle Problem Language Result Execution time Memory
103457 2019-03-30T18:31:34 Z popovicirobert Tropical Garden (IOI11_garden) C++14
69 / 100
 5000 ms 54560 KB 
#include <bits/stdc++.h>
#include "gardenlib.h"
#include "garden.h"

using namespace std;

typedef vector <int> VI;
typedef vector <VI> VVI;
typedef pair <int, int> PII;
typedef vector <PII> VPII;
typedef vector <VPII> VVPII;

void count_routes(int n, int m, int p, int R[][2], int q, int G[]) {
    VVI g(n + 1);
    int i;
    for(i = 0; i < m; i++) {
        R[i][0]++, R[i][1]++;
        g[R[i][0]].push_back(i);
        g[R[i][1]].push_back(i);
    }
    for(i = 1; i <= n; i++) {
        sort(g[i].begin(), g[i].end());
    }
    VVI anc(2 * n + 1, VI(30));
    for(i = 1; i <= n; i++) {
        int nod = (R[g[i][0]][0] ^ R[g[i][0]][1] ^ i);
        if(g[nod][0] == g[i][0]) {
            anc[i][0] = nod + n;
        }
        else {
            anc[i][0] = nod;
        }
        if(g[i].size() == 1) {
            if(g[nod][0] == g[i][0]) {
                anc[i + n][0] = nod + n;
            }
            else {
                anc[i + n][0] = nod;
            }
        }
        else {
            nod = (R[g[i][1]][0] ^ R[g[i][1]][1] ^ i);
            if(g[nod][0] == g[i][1]) {
                anc[i + n][0] = nod + n;
            }
            else {
                anc[i + n][0] = nod;
            }
        }
    }
    for(int bit = 1; bit < 30; bit++) {
        for(i = 1; i <= 2 * n; i++) {
            anc[i][bit] = anc[anc[i][bit - 1]][bit - 1];
        }
    }
    p++;
    for(int t = 0; t < q; t++) {
        int ans = 0;
        for(i = 1; i <= n; i++) {
            int nod = i;
            for(int bit = 0; (1 << bit) <= G[t]; bit++) {
                if(G[t] & (1 << bit)) {
                    nod = anc[nod][bit];
                    /*if(i == 1) {
                        cerr << nod << " ";
                    }*/
                }
            }
            if(nod == p || nod == n + p) {
                ans++;
            }
        }
        answer(ans);
    }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 632 KB Output is correct
2 Correct 3 ms 604 KB Output is correct
3 Correct 3 ms 732 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 760 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 3 ms 744 KB Output is correct
9 Correct 5 ms 860 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 632 KB Output is correct
2 Correct 3 ms 604 KB Output is correct
3 Correct 3 ms 732 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 760 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 3 ms 744 KB Output is correct
9 Correct 5 ms 860 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 37 ms 8440 KB Output is correct
12 Correct 78 ms 14172 KB Output is correct
13 Correct 194 ms 30968 KB Output is correct
14 Correct 361 ms 49288 KB Output is correct
15 Correct 359 ms 49872 KB Output is correct
16 Correct 276 ms 34100 KB Output is correct
17 Correct 191 ms 29064 KB Output is correct
18 Correct 74 ms 14084 KB Output is correct
19 Correct 358 ms 49280 KB Output is correct
20 Correct 404 ms 49876 KB Output is correct
21 Correct 258 ms 34168 KB Output is correct
22 Correct 189 ms 29052 KB Output is correct
23 Correct 482 ms 54560 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 632 KB Output is correct
2 Correct 3 ms 604 KB Output is correct
3 Correct 3 ms 732 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 760 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 3 ms 744 KB Output is correct
9 Correct 5 ms 860 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 37 ms 8440 KB Output is correct
12 Correct 78 ms 14172 KB Output is correct
13 Correct 194 ms 30968 KB Output is correct
14 Correct 361 ms 49288 KB Output is correct
15 Correct 359 ms 49872 KB Output is correct
16 Correct 276 ms 34100 KB Output is correct
17 Correct 191 ms 29064 KB Output is correct
18 Correct 74 ms 14084 KB Output is correct
19 Correct 358 ms 49280 KB Output is correct
20 Correct 404 ms 49876 KB Output is correct
21 Correct 258 ms 34168 KB Output is correct
22 Correct 189 ms 29052 KB Output is correct
23 Correct 482 ms 54560 KB Output is correct
24 Correct 8 ms 424 KB Output is correct
25 Execution timed out 5093 ms 8504 KB Time limit exceeded
26 Halted 0 ms 0 KB -