oj.uz

Submission #99224

# Submission time Handle Problem Language Result Execution time Memory
99224 2019-03-01T18:29:35 Z eriksuenderhauf Tropical Garden (IOI11_garden) C++11
100 / 100
 3741 ms 27408 KB 
#pragma GCC optimize("O3")
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
#define pri(n) printf("%d\n", (n))
#define pb push_back
using namespace std;
const int MAXN = 3e5 + 5;
int nx[31][MAXN];
int dist[MAXN][2], vis[MAXN];
vector<int> adj[MAXN];

void dfs(int u, int fr, int d, int tmp) {
    if (vis[u] && u != tmp) return;
    dist[u][fr] = d;
    if (u == tmp && d != 0)
        return;
    if (vis[u]) return;
    vis[u] = 1;
    for (int v: adj[u])
        dfs(v, fr, d + 1, tmp);
}

void count_routes(int n, int m, int p, int r[][2], int q, int g[]) {
    for (int i = 0; i < 2*n; i++)
        nx[0][i] = -1;
    for (int i = 0; i < m; i++) {
        int u = r[i][0], v = r[i][1];
        int f1 = 0, f2 = 0, f3 = 0, f4 = 0;
        if (nx[0][2*u] == -1) f1 = 1;
        if (nx[0][2*v] == -1) f2 = 1;
        if (nx[0][2*u+1] == -1) f3 = 1;
        if (nx[0][2*v+1] == -1) f4 = 1;
        if (f1) {
            if (f2) nx[0][2*u] = 2*v+1, adj[2*v+1].pb(2*u);
            else nx[0][2*u] = 2*v, adj[2*v].pb(2*u);
        } else if (f3) {
            if (f2) nx[0][2*u+1] = 2*v+1, adj[2*v+1].pb(2*u+1);
            else nx[0][2*u+1] = 2*v, adj[2*v].pb(2*u+1);
        }
        if (f2) {
            if (f1) nx[0][2*v] = 2*u+1, adj[2*u+1].pb(2*v);
            else nx[0][2*v] = 2*u, adj[2*u].pb(2*v);
        } else if (f4) {
            if (f1) nx[0][2*v+1] = 2*u+1, adj[2*u+1].pb(2*v+1);
            else nx[0][2*v+1] = 2*u, adj[2*u].pb(2*v+1);
        }
    }
    for (int i = 1; i < 2*n; i += 2)
        if (nx[0][i] == -1)
            nx[0][i] = nx[0][i - 1], adj[nx[0][i - 1]].pb(i);
    dfs(2*p,0,0,2*p);
    memset(vis, 0, sizeof vis);
    dfs(2*p+1,1,0,2*p+1);
    for (int i = 0; i < q; i++) {
        int ans = 0;
        for (int j = 0; j < n; j++) {
            if (dist[2*j][0] == 0 && dist[2*j][1] == 0)
                continue;
            if (dist[2*j][0] == g[i] || dist[2*j][1] == g[i]) {
                ans++;
                continue;
            }
            if (dist[2*p][0] != 0 && (g[i] - dist[2*j][0]) % dist[2*p][0] == 0 && g[i] > dist[2*j][0] && dist[2*j][0] != 0)
                ans++;
            else if (dist[2*p+1][1] != 0 && (g[i] - dist[2*j][1]) % dist[2*p+1][1] == 0 && g[i] > dist[2*j][1] && dist[2*j][1] != 0)
                ans++;
        }
        answer(ans);
    }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8612 KB Output is correct
2 Correct 10 ms 8696 KB Output is correct
3 Correct 10 ms 8668 KB Output is correct
4 Correct 10 ms 8540 KB Output is correct
5 Correct 11 ms 8568 KB Output is correct
6 Correct 11 ms 8672 KB Output is correct
7 Correct 10 ms 8612 KB Output is correct
8 Correct 11 ms 8604 KB Output is correct
9 Correct 11 ms 8796 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8612 KB Output is correct
2 Correct 10 ms 8696 KB Output is correct
3 Correct 10 ms 8668 KB Output is correct
4 Correct 10 ms 8540 KB Output is correct
5 Correct 11 ms 8568 KB Output is correct
6 Correct 11 ms 8672 KB Output is correct
7 Correct 10 ms 8612 KB Output is correct
8 Correct 11 ms 8604 KB Output is correct
9 Correct 11 ms 8796 KB Output is correct
10 Correct 10 ms 8568 KB Output is correct
11 Correct 20 ms 10268 KB Output is correct
12 Correct 33 ms 11384 KB Output is correct
13 Correct 55 ms 22028 KB Output is correct
14 Correct 98 ms 17956 KB Output is correct
15 Correct 136 ms 18184 KB Output is correct
16 Correct 101 ms 15548 KB Output is correct
17 Correct 93 ms 14540 KB Output is correct
18 Correct 39 ms 11312 KB Output is correct
19 Correct 102 ms 17796 KB Output is correct
20 Correct 130 ms 18100 KB Output is correct
21 Correct 103 ms 15580 KB Output is correct
22 Correct 93 ms 14684 KB Output is correct
23 Correct 108 ms 18624 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8612 KB Output is correct
2 Correct 10 ms 8696 KB Output is correct
3 Correct 10 ms 8668 KB Output is correct
4 Correct 10 ms 8540 KB Output is correct
5 Correct 11 ms 8568 KB Output is correct
6 Correct 11 ms 8672 KB Output is correct
7 Correct 10 ms 8612 KB Output is correct
8 Correct 11 ms 8604 KB Output is correct
9 Correct 11 ms 8796 KB Output is correct
10 Correct 10 ms 8568 KB Output is correct
11 Correct 20 ms 10268 KB Output is correct
12 Correct 33 ms 11384 KB Output is correct
13 Correct 55 ms 22028 KB Output is correct
14 Correct 98 ms 17956 KB Output is correct
15 Correct 136 ms 18184 KB Output is correct
16 Correct 101 ms 15548 KB Output is correct
17 Correct 93 ms 14540 KB Output is correct
18 Correct 39 ms 11312 KB Output is correct
19 Correct 102 ms 17796 KB Output is correct
20 Correct 130 ms 18100 KB Output is correct
21 Correct 103 ms 15580 KB Output is correct
22 Correct 93 ms 14684 KB Output is correct
23 Correct 108 ms 18624 KB Output is correct
24 Correct 11 ms 8568 KB Output is correct
25 Correct 106 ms 10304 KB Output is correct
26 Correct 131 ms 11452 KB Output is correct
27 Correct 1479 ms 22300 KB Output is correct
28 Correct 1347 ms 18052 KB Output is correct
29 Correct 2765 ms 18108 KB Output is correct
30 Correct 1636 ms 15748 KB Output is correct
31 Correct 1143 ms 14544 KB Output is correct
32 Correct 139 ms 11284 KB Output is correct
33 Correct 1350 ms 17808 KB Output is correct
34 Correct 2703 ms 17960 KB Output is correct
35 Correct 1092 ms 15424 KB Output is correct
36 Correct 1692 ms 14572 KB Output is correct
37 Correct 922 ms 18532 KB Output is correct
38 Correct 3741 ms 27408 KB Output is correct