Submission #851583

#	Time	Username	Problem	Language	Result	Execution time	Memory
851583		12345678	Tropical Garden (IOI11_garden)	C++17	0 / 100	549 ms	262144 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include "bits/stdc++.h"

using namespace std;

const int nx=1e4+5;
int mx[nx][2], ans;
vector<pair<int, int>> d[nx];

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    for (int i=M-1; i>=0; i--)
    {
        d[R[i][0]].push_back({R[i][1], i+1});
        d[R[i][1]].push_back({R[i][0], i+1});
        mx[R[i][0]][1]=mx[R[i][0]][0]; mx[R[i][0]][0]=i+1;
        mx[R[i][1]][1]=mx[R[i][1]][0]; mx[R[i][1]][0]=i+1;
    }
    for (int i=0; i<N; i++) if (mx[i][1]==0) mx[i][1]=mx[i][0];
    queue<pair<pair<int, int>, bool>> q;
    q.push({{P, 0}, 0});
    while (!q.empty())
    {
        auto u=q.front().first.first, k=q.front().first.second;
        auto ism=q.front().second;
        q.pop();
        if (k==G[0]) 
        {
            if (!ism) ans++;
            continue;
        }
        if (ism) 
        {
            int v=R[mx[u][0]-1][0]==u?R[mx[u][0]-1][1]:R[mx[u][0]-1][0];
            q.push({{v, k+1}, mx[v][0]==mx[u][0]?false:true});
            continue;
        }
        for (auto [v, p]:d[u])
        {
            if (p==mx[v][0]) q.push({{v, k+1}, 0});
            if (p==mx[v][1]) q.push({{v, k+1}, 1});
        }
    }
    answer(ans);
}

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