oj.uz

Submission #1114302

# Submission time Handle Problem Language Result Execution time Memory
1114302 2024-11-18T13:51:13 Z usukhbaatar Tropical Garden (IOI11_garden) C++17
49 / 100
 5000 ms 3880 KB 
#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
using namespace std;

int n, m, fn;
vector<vector<pair<int, int>>> a;
vector<int> g;
vector<bool> vis;
vector<bool> start;
vector<bool> finish;

void dfs(int u, int p, int i) {
    int x = (i << 1) + (p > u);
    if (x >= 0 && vis[x]) return;
    if (x != -1) vis[x] = 1;
    if (a[u].size() == 0) return;
    if (i != -1 && u == fn) finish[x] = 1; 
    int id = (a[u].size() == 1 || a[u][0].second != i) ? 0 : 1;
    int v = a[u][id].first;
    int j = a[u][id].second;
    int y = (j << 1) + (v < u);
    if (x != -1) {
        if (g[x] != -1 && g[x] != y) exit(1);
        g[x] = y;
    }
    else start[y] = 1;
    dfs(v, u, j);
}

bool check(int u, int k) {
    for (int i = 0; i < k - 1; i++) {
        u = g[u];
        if (u == -1) return 0;
    }
    return finish[u];
}

void count_routes(int N, int M, int P, int ed[][2], int q, int qry[]) {
    n = N, m = (M << 1), fn = P;
    a.resize(n);
    vis.resize(m, 0);
    g.resize(m, -1);
    start.resize(m, 0);
    finish.resize(m, 0);

    for (int i = 0; i < M; i++) {
        int u = ed[i][0], v = ed[i][1];
        if (a[u].size() < 2) a[u].push_back({v, i});
        if (a[v].size() < 2) a[v].push_back({u, i});
    }
    
    for (int u = 0; u < n; u++) {
        dfs(u, n, -1);
    }

    for (int i = 0; i < q; i++) {
        int ans = 0;
        for (int u = 0; u < m; u++) {
            if (start[u] && check(u, qry[i])) {
                ans++;
            }
        }
        answer(ans);
    }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 2 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 2 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 2 ms 336 KB Output is correct
9 Correct 3 ms 592 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 2 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 2 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 2 ms 336 KB Output is correct
9 Correct 3 ms 592 KB Output is correct
10 Correct 3 ms 336 KB Output is correct
11 Execution timed out 5076 ms 3880 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 2 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 2 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 2 ms 336 KB Output is correct
9 Correct 3 ms 592 KB Output is correct
10 Correct 3 ms 336 KB Output is correct
11 Execution timed out 5076 ms 3880 KB Time limit exceeded
12 Halted 0 ms 0 KB -