oj.uz

Submission #1076417

# Submission time Handle Problem Language Result Execution time Memory
1076417 2024-08-26T13:42:33 Z ArthuroWich Tropical Garden (IOI11_garden) C++17
100 / 100
 1363 ms 76276 KB 
#include "garden.h"
#include "gardenlib.h"
#include<bits/stdc++.h>
using namespace std;
int n, m, p, ans = 0;
vector<int> adj[150005], radj[300005];
int succ[300005][31], vis1[300005], vis2[300005], dep1[300005], dep2[300005], cyc1 = -1, cyc2 = -1;
void initsucc() {
    for (int j = 1; j < 31; j++) {
        for (int i = 0; i <= 2*n; i++) {
            succ[i][j] = succ[succ[i][j-1]][j-1];
        }
    }
}
void calc(int a, int k) {
    for (int i = 0; i < 31; i++) {
        if (k & (1 << i)) {
            a = succ[a][i];
        }
    }
    if (a == p || a == p+n) {
        ans++;
    }
}
void dfs1(int i, int st, int d) {
    if (vis1[i] && st == i && cyc1 == -1) {
        cyc1 = d;
        return;
    }
    if (vis1[i]) {
        return;
    }
    vis1[i] = 1;
    dep1[i] = d;
    for (int j : radj[i]) {
        dfs1(j, st, d+1);
    }
}
void dfs2(int i, int st, int d) {
    if (vis2[i] && st == i && cyc2 == -1) {
        cyc2 = d;
        return;
    }
    if (vis2[i]) {
        return;
    }
    vis2[i] = 1;
    dep2[i] = d;
    for (int j : radj[i]) {
        dfs2(j, st, d+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++) {
        if (adj[R[i][0]].size() < 2) {
            adj[R[i][0]].push_back(R[i][1]);
        }
        if (adj[R[i][1]].size() < 2) {
            adj[R[i][1]].push_back(R[i][0]);
        }
    }
    for (int i = 0; i < n; i++) {
        if (adj[i].size() == 1) {
            if (i == adj[adj[i][0]][0]) {
                succ[i][0] = adj[i][0]+n;
            } else {
                succ[i][0] = adj[i][0];
            }
            succ[i+n][0] = succ[i][0];
        } else {
            if (i == adj[adj[i][0]][0]) {
                succ[i][0] = adj[i][0]+n;
            } else {
                succ[i][0] = adj[i][0];
            }
            if (i == adj[adj[i][1]][0]) {
                succ[i+n][0] = adj[i][1]+n;
            } else {
                succ[i+n][0] = adj[i][1];
            }
        }
    }
    initsucc();
    if (Q == 1) {
        ans = 0;
        for (int i = 0; i < n; i++) {
            calc(i, G[0]);
        }
        answer(ans);
        return;
    } 
    for (int i = 0; i < 2*n; i++) {
        radj[succ[i][0]].push_back(i);
    }
    dfs1(p, p, 0);
    dfs2(p+n, p+n, 0);
    for (int j = 0; j < Q; j++) {
        ans = 0;
        for (int i = 0; i < n; i++) {
            bool f1 = 0, f2 = 0;
            int k = G[j];
            if (vis1[i]) {
                k -= dep1[i];
                if (k == 0) {
                    f1 = 1;
                } else if (cyc1 != -1 && k % cyc1 == 0) {
                    f1 = 1;
                }
            }
            k = G[j];
            if (vis2[i]) {
                k -= dep2[i];
                if (k == 0) {
                    f2 = 1;
                } else if (cyc2 != -1 && k % cyc2 == 0) {
                    f2 = 1;
                }
            }
            if (f1 || f2) {
                ans++;
            }
        }
        answer(ans);
    }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11100 KB Output is correct
2 Correct 8 ms 11312 KB Output is correct
3 Correct 5 ms 11100 KB Output is correct
4 Correct 5 ms 10844 KB Output is correct
5 Correct 5 ms 10876 KB Output is correct
6 Correct 5 ms 11336 KB Output is correct
7 Correct 5 ms 11060 KB Output is correct
8 Correct 5 ms 11100 KB Output is correct
9 Correct 8 ms 11264 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11100 KB Output is correct
2 Correct 8 ms 11312 KB Output is correct
3 Correct 5 ms 11100 KB Output is correct
4 Correct 5 ms 10844 KB Output is correct
5 Correct 5 ms 10876 KB Output is correct
6 Correct 5 ms 11336 KB Output is correct
7 Correct 5 ms 11060 KB Output is correct
8 Correct 5 ms 11100 KB Output is correct
9 Correct 8 ms 11264 KB Output is correct
10 Correct 5 ms 10844 KB Output is correct
11 Correct 18 ms 17556 KB Output is correct
12 Correct 27 ms 22108 KB Output is correct
13 Correct 49 ms 35756 KB Output is correct
14 Correct 94 ms 50768 KB Output is correct
15 Correct 88 ms 51292 KB Output is correct
16 Correct 77 ms 38648 KB Output is correct
17 Correct 56 ms 34484 KB Output is correct
18 Correct 30 ms 22100 KB Output is correct
19 Correct 97 ms 50772 KB Output is correct
20 Correct 92 ms 51284 KB Output is correct
21 Correct 63 ms 38480 KB Output is correct
22 Correct 53 ms 34388 KB Output is correct
23 Correct 108 ms 54812 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11100 KB Output is correct
2 Correct 8 ms 11312 KB Output is correct
3 Correct 5 ms 11100 KB Output is correct
4 Correct 5 ms 10844 KB Output is correct
5 Correct 5 ms 10876 KB Output is correct
6 Correct 5 ms 11336 KB Output is correct
7 Correct 5 ms 11060 KB Output is correct
8 Correct 5 ms 11100 KB Output is correct
9 Correct 8 ms 11264 KB Output is correct
10 Correct 5 ms 10844 KB Output is correct
11 Correct 18 ms 17556 KB Output is correct
12 Correct 27 ms 22108 KB Output is correct
13 Correct 49 ms 35756 KB Output is correct
14 Correct 94 ms 50768 KB Output is correct
15 Correct 88 ms 51292 KB Output is correct
16 Correct 77 ms 38648 KB Output is correct
17 Correct 56 ms 34484 KB Output is correct
18 Correct 30 ms 22100 KB Output is correct
19 Correct 97 ms 50772 KB Output is correct
20 Correct 92 ms 51284 KB Output is correct
21 Correct 63 ms 38480 KB Output is correct
22 Correct 53 ms 34388 KB Output is correct
23 Correct 108 ms 54812 KB Output is correct
24 Correct 6 ms 11096 KB Output is correct
25 Correct 61 ms 18872 KB Output is correct
26 Correct 89 ms 24148 KB Output is correct
27 Correct 743 ms 52152 KB Output is correct
28 Correct 730 ms 59516 KB Output is correct
29 Correct 886 ms 60100 KB Output is correct
30 Correct 464 ms 44104 KB Output is correct
31 Correct 479 ms 39764 KB Output is correct
32 Correct 100 ms 24292 KB Output is correct
33 Correct 720 ms 59080 KB Output is correct
34 Correct 813 ms 60044 KB Output is correct
35 Correct 444 ms 44164 KB Output is correct
36 Correct 803 ms 39928 KB Output is correct
37 Correct 516 ms 62708 KB Output is correct
38 Correct 1363 ms 76276 KB Output is correct