Submission #298257

#	Time	Username	Problem	Language	Result	Execution time	Memory
298257		tatyam	Tropical Garden (IOI11_garden)	C++17	100 / 100	2906 ms	25748 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<int> next(N * 2);
    vector rev(N * 2, vector<int>());
    for(int i = 0; i < N; i++){
        {
            const auto [a, b] = g[i][0];
            if(a != INF){
                next[i * 2] = b * 2 + (a == g[b][0].first);
                rev[next[i * 2]].push_back(i * 2);
            }
        }
        {
            const auto [a, b] = g[i][1];
            if(a != INF){
                next[i * 2 + 1] = b * 2 + (a == g[b][0].first);
                rev[next[i * 2 + 1]].push_back(i * 2 + 1);
            }
        }
    }
    const int t1 = [&]{
        int at = P * 2;
        for(int i = 1; i <= N * 2; i++){
            at = next[at];
            if(at == P * 2) return i;
        }
        return INF;
    }();
    const int t2 = [&]{
        int at = P * 2 + 1;
        for(int i = 1; i <= N * 2; i++){
            at = next[at];
            if(at == P * 2 + 1) return i;
        }
        return INF;
    }();
    vector f1(N * 2, INF), f2(N * 2, INF);
    queue<int> q;
    f1[P * 2] = 0;
    q.push(P * 2);
    while(q.size()){
        int at = q.front();
        q.pop();
        for(int i : rev[at]) if(chmin(f1[i], f1[at] + 1)) q.push(i);
    }
    f2[P * 2 + 1] = 0;
    q.push(P * 2 + 1);
    while(q.size()){
        int at = q.front();
        q.pop();
        for(int i : rev[at]) if(chmin(f2[i], f2[at] + 1)) q.push(i);
    }
    for(int i = 0; i < Q; i++){
        const int K = G[i];
        int ans = 0;
        for(int i = 0; i < N; i++) ans += K >= f1[i * 2] && (K - f1[i * 2]) % t1 == 0 || K >= f2[i * 2] && (K - f2[i * 2]) % t2 == 0;
        answer(ans);
    }
}

Compilation message (stderr)

garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:71:58: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   71 |         for(int i = 0; i < N; i++) ans += K >= f1[i * 2] && (K - f1[i * 2]) % t1 == 0 || K >= f2[i * 2] && (K - f2[i * 2]) % t2 == 0;
      |                                           ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 49 / 49
• Subtask 2: 20 / 20
• Subtask 3: 31 / 31