oj.uz

Submission #298240

# Submission time Handle Problem Language Result Execution time Memory
298240 2020-09-12T16:05:07 Z tatyam Tropical Garden (IOI11_garden) C++17
69 / 100
 5000 ms 41976 KB 
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int INF = 0x3fffffff;
template<class T> bool chmin(T& a, const T& b){ if(a > b){ a = b; return 1; } return 0; }

void answer(int x);

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
    vector g(N, array{pii{INF, -1}, pii{INF, -1}});
    // 各頂点から最も美しい 2 つの辺を持つ
    for(int i = 0; i < M; i++){
        auto [a, b] = R[i];
        if(chmin(g[a][1], {i, b}) && g[a][1] < g[a][0]) swap(g[a][0], g[a][1]);
        if(chmin(g[b][1], {i, a}) && g[b][1] < g[b][0]) swap(g[b][0], g[b][1]);
    }
    for(auto& [e1, e2] : g) if(e2.first == INF) e2 = e1;
    vector next(30, vector<int>(N * 2));
    // ダブリング
    for(int i = 0; i < N; i++){
        {
            const auto [a, b] = g[i][0];
            if(a != INF) next[0][i * 2] = b * 2 + (a == g[b][0].first);
        }
        {
            const auto [a, b] = g[i][1];
            if(a != INF) next[0][i * 2 + 1] = b * 2 + (a == g[b][0].first);
        }
    }
    for(int i = 0; i < 29; i++) for(int j = 0; j < N * 2; j++) next[i + 1][j] = next[i][next[i][j]];
    for(int i = 0; i < Q; i++){
        const int K = G[i];
        int ans = 0;
        for(int i = 0; i < N; i++){
            int at = i * 2;
            for(int i = 0; K >> i; i++) if(K >> i & 1) at = next[i][at];
            ans += at / 2 == P;
        }
        answer(ans);
    }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 544 KB Output is correct
4 Correct 1 ms 288 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 640 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 640 KB Output is correct
9 Correct 3 ms 768 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 544 KB Output is correct
4 Correct 1 ms 288 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 640 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 640 KB Output is correct
9 Correct 3 ms 768 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 14 ms 6528 KB Output is correct
12 Correct 29 ms 11156 KB Output is correct
13 Correct 50 ms 24184 KB Output is correct
14 Correct 91 ms 38020 KB Output is correct
15 Correct 104 ms 38648 KB Output is correct
16 Correct 73 ms 26616 KB Output is correct
17 Correct 67 ms 22720 KB Output is correct
18 Correct 28 ms 11128 KB Output is correct
19 Correct 96 ms 38008 KB Output is correct
20 Correct 93 ms 38520 KB Output is correct
21 Correct 71 ms 26616 KB Output is correct
22 Correct 70 ms 22776 KB Output is correct
23 Correct 103 ms 41976 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 544 KB Output is correct
4 Correct 1 ms 288 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 640 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 640 KB Output is correct
9 Correct 3 ms 768 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 14 ms 6528 KB Output is correct
12 Correct 29 ms 11156 KB Output is correct
13 Correct 50 ms 24184 KB Output is correct
14 Correct 91 ms 38020 KB Output is correct
15 Correct 104 ms 38648 KB Output is correct
16 Correct 73 ms 26616 KB Output is correct
17 Correct 67 ms 22720 KB Output is correct
18 Correct 28 ms 11128 KB Output is correct
19 Correct 96 ms 38008 KB Output is correct
20 Correct 93 ms 38520 KB Output is correct
21 Correct 71 ms 26616 KB Output is correct
22 Correct 70 ms 22776 KB Output is correct
23 Correct 103 ms 41976 KB Output is correct
24 Correct 6 ms 384 KB Output is correct
25 Correct 2364 ms 6656 KB Output is correct
26 Correct 4769 ms 11128 KB Output is correct
27 Execution timed out 5094 ms 24056 KB Time limit exceeded
28 Halted 0 ms 0 KB -