제출 #298240

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
298240		tatyam	Tropical Garden (IOI11_garden)	C++17	69 / 100	5094 ms	41976 KiB

garden

#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 / 49
• Subtask 2: 20 / 20
• Subtask 3: 0 / 31