oj.uz

Submission #119962

# Submission time Handle Problem Language Result Execution time Memory
119962 2019-06-22T19:15:39 Z Osama_Alkhodairy Tropical Garden (IOI11_garden) C++17
49 / 100
 9 ms 4444 KB 
#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
//~ #include "grader.cpp"
using namespace std;

const int maxn = 150001;

int n, m, p, g[maxn][101];
vector <int> v[maxn];

int go(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];
}
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++){
        g[node][0] = node;
        for(int step = 1 ; step <= 100 ; step++){
            int cur = g[node][step - 1];
            int prev = -1;
            if(step - 2 >= 0) prev = g[node][step - 2];
            g[node][step] = go(cur, prev);
        }
    }
    vector <int> ans(101);
    for(int step = 1 ; step <= 100 ; step++){
        for(int node = 0 ; node < n ; node++){
            ans[step] += g[node][step] == p;
        }
    }
    for(int i = 0 ; i < Q ; i++){
        answer(ans[G[i]]);
    }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4216 KB Output is correct
2 Correct 6 ms 4216 KB Output is correct
3 Correct 6 ms 4344 KB Output is correct
4 Correct 5 ms 3932 KB Output is correct
5 Correct 3 ms 3932 KB Output is correct
6 Correct 6 ms 4344 KB Output is correct
7 Correct 5 ms 3832 KB Output is correct
8 Correct 6 ms 4344 KB Output is correct
9 Correct 9 ms 4444 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4216 KB Output is correct
2 Correct 6 ms 4216 KB Output is correct
3 Correct 6 ms 4344 KB Output is correct
4 Correct 5 ms 3932 KB Output is correct
5 Correct 3 ms 3932 KB Output is correct
6 Correct 6 ms 4344 KB Output is correct
7 Correct 5 ms 3832 KB Output is correct
8 Correct 6 ms 4344 KB Output is correct
9 Correct 9 ms 4444 KB Output is correct
10 Incorrect 5 ms 3832 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4216 KB Output is correct
2 Correct 6 ms 4216 KB Output is correct
3 Correct 6 ms 4344 KB Output is correct
4 Correct 5 ms 3932 KB Output is correct
5 Correct 3 ms 3932 KB Output is correct
6 Correct 6 ms 4344 KB Output is correct
7 Correct 5 ms 3832 KB Output is correct
8 Correct 6 ms 4344 KB Output is correct
9 Correct 9 ms 4444 KB Output is correct
10 Incorrect 5 ms 3832 KB Output isn't correct
11 Halted 0 ms 0 KB -