oj.uz

Submission #851580

# Submission time Handle Problem Language Result Execution time Memory
851580 2023-09-20T07:35:45 Z 12345678 Tropical Garden (IOI11_garden) C++17
0 / 100
 493 ms 262144 KB 
#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<tuple<int, int, bool>> q;
    q.push({P, 0, 0});
    while (!q.empty())
    {
        auto [u, k, ism]=q.front();
        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.0

# Verdict Execution time Memory Grader output
1 Runtime error 493 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 493 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 493 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -