oj.uz

답안 #298240

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -