oj.uz

Submission #447627

# Submission time Handle Problem Language Result Execution time Memory
447627 2021-07-27T07:02:24 Z dxz05 Tropical Garden (IOI11_garden) C++14
49 / 100
 5000 ms 4992 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>

const int MAXN = 155555;

using namespace std;

vector<int> g[MAXN];

int dfs(int v, int p, int k){
    if (k == 0) return v;
    if (g[v].size() == 1 || g[v][0] != p) return dfs(g[v][0], v, k - 1);
    return dfs(g[v][1], v, k - 1);
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
    for (int i = 0; i < M; i++){
        g[R[i][0]].push_back(i);
        g[R[i][1]].push_back(i);
    }

    for (int i = 0; i < N; i++){
        if (g[i].size() < 2) continue;

        int j = min_element(g[i].begin(), g[i].end()) - g[i].begin();
        swap(g[i][0], g[i][j]);

        j = min_element(g[i].begin() + 1, g[i].end()) - g[i].begin();
        swap(g[i][1], g[i][j]);

        g[i].resize(2);
    }

    for (int i = 0; i < N; i++){
        int x = g[i][0];
        g[i][0] = (R[x][0] == i ? R[x][1] : R[x][0]);

        if (g[i].size() == 2){
            x = g[i][1];
            g[i][1] = (R[x][0] == i ? R[x][1] : R[x][0]);
        }

    }

    for (int it = 0; it < Q; it++){
        int ans = 0;
        for (int i = 0; i < N; i++){
            if (dfs(i, i, G[it]) == P) ans++;
        }
        answer(ans);
    }

}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3960 KB Output is correct
2 Correct 3 ms 3916 KB Output is correct
3 Correct 3 ms 3968 KB Output is correct
4 Correct 3 ms 3916 KB Output is correct
5 Correct 3 ms 3916 KB Output is correct
6 Correct 4 ms 3968 KB Output is correct
7 Correct 3 ms 3952 KB Output is correct
8 Correct 3 ms 3916 KB Output is correct
9 Correct 5 ms 4172 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3960 KB Output is correct
2 Correct 3 ms 3916 KB Output is correct
3 Correct 3 ms 3968 KB Output is correct
4 Correct 3 ms 3916 KB Output is correct
5 Correct 3 ms 3916 KB Output is correct
6 Correct 4 ms 3968 KB Output is correct
7 Correct 3 ms 3952 KB Output is correct
8 Correct 3 ms 3916 KB Output is correct
9 Correct 5 ms 4172 KB Output is correct
10 Correct 8 ms 3916 KB Output is correct
11 Execution timed out 5068 ms 4992 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3960 KB Output is correct
2 Correct 3 ms 3916 KB Output is correct
3 Correct 3 ms 3968 KB Output is correct
4 Correct 3 ms 3916 KB Output is correct
5 Correct 3 ms 3916 KB Output is correct
6 Correct 4 ms 3968 KB Output is correct
7 Correct 3 ms 3952 KB Output is correct
8 Correct 3 ms 3916 KB Output is correct
9 Correct 5 ms 4172 KB Output is correct
10 Correct 8 ms 3916 KB Output is correct
11 Execution timed out 5068 ms 4992 KB Time limit exceeded
12 Halted 0 ms 0 KB -