oj.uz

Submission #119986

# Submission time Handle Problem Language Result Execution time Memory
119986 2019-06-22T21:12:11 Z Osama_Alkhodairy Tropical Garden (IOI11_garden) C++17
69 / 100
 5000 ms 82732 KB 
#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
//~ #include "grader.cpp"
using namespace std;

const int maxn = 150001;
const int maxk = 31;

int n, m, p;
pair <int, int> g[maxn][maxk][2];
vector <int> v[maxn];

int go1(int node, int prev){
    if(v[node].size() == 1) return v[node][0];
    if(v[node][0] == prev) return v[node][1];
    return v[node][0];
}
int go2(int node, int idx){
    if(v[node].size() == 1) return v[node][0];
    if(idx == 1) return v[node][0];
    return v[node][1];
}
int calc(int node, int steps){
    int prev = -1;
    while(steps--){
        int pcur = node;
        node = go1(node, prev);
        prev = pcur;
    }
    return node;
}
int lift(int node, int s){
    pair <int, int> cur = make_pair(node, 1);
    for(int i = maxk - 1 ; i >= 0 ; i--){
        if((s >> i) & 1){
            cur = g[cur.first][i][cur.second];
        }
    }
    return cur.first;
}
int idx(int node, int h){
    if(v[node][0] == h) return 0;
    return 1;
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
    n = N;
    m = M;
    p = P;
    for(int i = 0 ; i < M ; i++){
        v[R[i][0]].push_back(R[i][1]);
        v[R[i][1]].push_back(R[i][0]);
    }
    for(int node = 0 ; node < n ; node++){
        for(int k = 0 ; k < 2 ; k++){
            int nxt = go2(node, k);
            g[node][0][k] = make_pair(nxt, idx(nxt, node));
        }
    }
    for(int j = 1 ; j < maxk ; j++){
        for(int node = 0 ; node < n ; node++){
            for(int k = 0 ; k < 2 ; k++){
                auto c = g[node][j - 1][k];
                auto nxt = g[c.first][j - 1][c.second];
                g[node][j][k] = nxt;
            }
        }
    }
    for(int i = 0 ; i < Q ; i++){
        int ans = 0;
        for(int node = 0 ; node < n ; node++){
            ans += lift(node, G[i]) == p;
        }
        answer(ans);
    }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4304 KB Output is correct
2 Correct 6 ms 4316 KB Output is correct
3 Correct 6 ms 4472 KB Output is correct
4 Correct 5 ms 3836 KB Output is correct
5 Correct 5 ms 3832 KB Output is correct
6 Correct 6 ms 4344 KB Output is correct
7 Correct 6 ms 3932 KB Output is correct
8 Correct 6 ms 4344 KB Output is correct
9 Correct 8 ms 4572 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4304 KB Output is correct
2 Correct 6 ms 4316 KB Output is correct
3 Correct 6 ms 4472 KB Output is correct
4 Correct 5 ms 3836 KB Output is correct
5 Correct 5 ms 3832 KB Output is correct
6 Correct 6 ms 4344 KB Output is correct
7 Correct 6 ms 3932 KB Output is correct
8 Correct 6 ms 4344 KB Output is correct
9 Correct 8 ms 4572 KB Output is correct
10 Correct 5 ms 3960 KB Output is correct
11 Correct 44 ms 15684 KB Output is correct
12 Correct 71 ms 23784 KB Output is correct
13 Correct 199 ms 48476 KB Output is correct
14 Correct 258 ms 74976 KB Output is correct
15 Correct 263 ms 76024 KB Output is correct
16 Correct 190 ms 52728 KB Output is correct
17 Correct 151 ms 45212 KB Output is correct
18 Correct 66 ms 23800 KB Output is correct
19 Correct 266 ms 74916 KB Output is correct
20 Correct 264 ms 75624 KB Output is correct
21 Correct 188 ms 52728 KB Output is correct
22 Correct 157 ms 45128 KB Output is correct
23 Correct 309 ms 82732 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4304 KB Output is correct
2 Correct 6 ms 4316 KB Output is correct
3 Correct 6 ms 4472 KB Output is correct
4 Correct 5 ms 3836 KB Output is correct
5 Correct 5 ms 3832 KB Output is correct
6 Correct 6 ms 4344 KB Output is correct
7 Correct 6 ms 3932 KB Output is correct
8 Correct 6 ms 4344 KB Output is correct
9 Correct 8 ms 4572 KB Output is correct
10 Correct 5 ms 3960 KB Output is correct
11 Correct 44 ms 15684 KB Output is correct
12 Correct 71 ms 23784 KB Output is correct
13 Correct 199 ms 48476 KB Output is correct
14 Correct 258 ms 74976 KB Output is correct
15 Correct 263 ms 76024 KB Output is correct
16 Correct 190 ms 52728 KB Output is correct
17 Correct 151 ms 45212 KB Output is correct
18 Correct 66 ms 23800 KB Output is correct
19 Correct 266 ms 74916 KB Output is correct
20 Correct 264 ms 75624 KB Output is correct
21 Correct 188 ms 52728 KB Output is correct
22 Correct 157 ms 45128 KB Output is correct
23 Correct 309 ms 82732 KB Output is correct
24 Correct 14 ms 3916 KB Output is correct
25 Execution timed out 5053 ms 15724 KB Time limit exceeded
26 Halted 0 ms 0 KB -