oj.uz

Submission #851583

# Submission time Handle Problem Language Result Execution time Memory
851583 2023-09-20T07:38:54 Z 12345678 Tropical Garden (IOI11_garden) C++17
0 / 100
 549 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<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.0

# Verdict Execution time Memory Grader output
1 Runtime error 549 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 549 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 549 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -