Submission #851579

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

garden

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

using namespace std;

const int nx=1e3+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<tuple<int, int, bool>> q;
    q.push({P, 0, 0});
    while (!q.empty())
    {
        auto [u, k, ism]=q.front();
        //cout<<u<<' '<<k<<' '<<ism<<'\n';
        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]?0:1});
            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