oj.uz

Submission #103459

# Submission time Handle Problem Language Result Execution time Memory
103459 2019-03-30T18:36:13 Z popovicirobert Tropical Garden (IOI11_garden) C++14
69 / 100
 5000 ms 54496 KB 
#include <bits/stdc++.h>
#include "gardenlib.h"
#include "garden.h"
#define lsb(x) (x & (-x))

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;
            }
        }
    }
    unordered_map <int, int> mp;
    for(int bit = 0; bit < 30; bit++) {
        mp[1 << bit] = bit;
    }
    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, aux = G[t];
            while(aux > 0) {
                int cur = lsb(aux);
                nod = anc[nod][mp[cur]];
                aux -= cur;
            }
            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 632 KB Output is correct
3 Correct 3 ms 632 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 4 ms 732 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 3 ms 760 KB Output is correct
9 Correct 5 ms 760 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 632 KB Output is correct
3 Correct 3 ms 632 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 4 ms 732 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 3 ms 760 KB Output is correct
9 Correct 5 ms 760 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 38 ms 8488 KB Output is correct
12 Correct 89 ms 14204 KB Output is correct
13 Correct 205 ms 31084 KB Output is correct
14 Correct 396 ms 49280 KB Output is correct
15 Correct 436 ms 49884 KB Output is correct
16 Correct 316 ms 34212 KB Output is correct
17 Correct 192 ms 29028 KB Output is correct
18 Correct 82 ms 14108 KB Output is correct
19 Correct 414 ms 49288 KB Output is correct
20 Correct 387 ms 49788 KB Output is correct
21 Correct 258 ms 34164 KB Output is correct
22 Correct 190 ms 29008 KB Output is correct
23 Correct 531 ms 54496 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 632 KB Output is correct
3 Correct 3 ms 632 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 4 ms 732 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 3 ms 760 KB Output is correct
9 Correct 5 ms 760 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 38 ms 8488 KB Output is correct
12 Correct 89 ms 14204 KB Output is correct
13 Correct 205 ms 31084 KB Output is correct
14 Correct 396 ms 49280 KB Output is correct
15 Correct 436 ms 49884 KB Output is correct
16 Correct 316 ms 34212 KB Output is correct
17 Correct 192 ms 29028 KB Output is correct
18 Correct 82 ms 14108 KB Output is correct
19 Correct 414 ms 49288 KB Output is correct
20 Correct 387 ms 49788 KB Output is correct
21 Correct 258 ms 34164 KB Output is correct
22 Correct 190 ms 29008 KB Output is correct
23 Correct 531 ms 54496 KB Output is correct
24 Correct 22 ms 380 KB Output is correct
25 Execution timed out 5074 ms 8500 KB Time limit exceeded
26 Halted 0 ms 0 KB -