oj.uz

Submission #763451

# Submission time Handle Problem Language Result Execution time Memory
763451 2023-06-22T10:09:37 Z boris_mihov Tropical Garden (IOI11_garden) C++17
49 / 100
 5000 ms 5388 KB 
#include "garden.h"
#include "gardenlib.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cstring>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 150000 + 10;
const int INF  = 1e9;

int n, m, p, q;
int dp[MAXN][2];
int cnt[MAXN][2];
int cnt2[MAXN][2];
std::pair <int,int> dfsReach[MAXN];
std::vector <std::pair <int,int>> g[MAXN];
bool vis[MAXN][2];

void dfs(int node, bool next, int edges, bool firstEdge)
{
    if (next == false)
    {
        dfsReach[node] = {edges, firstEdge};
        cnt[edges][firstEdge]++;
    }

    int l = 0, r = g[node].size();
    if (next || g[node].size() == 1)
    {
        r = 1;
    } else
    {
        l = 1;
    }

    for (int i = l ; i < r ; ++i)
    {
        auto [u, t] = g[node][i];
        if (u == p)
        {
            continue;
        }

        if (t == g[u][0].second)
        {
            dfs(u, 0, edges + 1, firstEdge);
            continue;
        }

        if (t == g[u][1].second)
        {
            dfs(u, 1, edges + 1, firstEdge);
            continue;
        }
    }
}

int g1;
std::pair <int,int> dfsCycle(int node, bool fromMAX, int time)
{
    if (time > g1)
    {
        return {0, 0};
    }

    if (time == g1)
    {
        return {(node == p), 1};
    }
 
    if (!fromMAX || g[node].size() == 1)
    {
        return dfsCycle(g[node][0].first, (g[node][0].second == g[g[node][0].first][0].second), time + 1);
    } else
    {
        return dfsCycle(g[node][1].first, (g[node][1].second == g[g[node][1].first][0].second), time + 1);
    }
}

std::pair <int,int> reach(int node, bool fromMAX, int time)
{
    if (node == p)
    {
        return {time, fromMAX};
    }
 
    if (vis[node][fromMAX])
    {
        return {-1, -1};
    }

    vis[node][fromMAX] = true;
    if (!fromMAX || g[node].size() == 1)
    {
        return reach(g[node][0].first, (g[node][0].second == g[g[node][0].first][0].second), time + 1);
    } else
    {
        return reach(g[node][1].first, (g[node][1].second == g[g[node][1].first][0].second), time + 1);
    }
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    n = N;
    m = M;
    p = P + 1;
    q = Q;

    for (int i = 0 ; i < m ; ++i)
    {
        g[R[i][0] + 1].push_back({R[i][1] + 1, i + 1});
        g[R[i][1] + 1].push_back({R[i][0] + 1, i + 1});
    }

    for (int i = 1 ; i <= n ; ++i)
    {
        dfsReach[i] = {-1, -1};
        std::sort(g[i].begin(), g[i].end(), [&](auto a, auto b)
        {
            return a.second < b.second;
        });
    }

    vis[p][0] = vis[p][1] = true;
    for (const auto &[u, t] : g[p])
    {
        if (t == g[u][0].second)
        {
            dfs(u, 0, 1, (t == g[p][0].second));
            continue;
        } 

        if (t == g[u][1].second)
        {
            dfs(u, 1, 1, (t == g[p][0].second));
            continue;
        }
    }

    cnt[0][0]++;
    for (int i = 1 ; i <= n ; ++i)
    {
        if (i == p)
        {
            continue;
        }

        for (int j = 1 ; j <= n ; ++j)
        {
            vis[j][0] = vis[j][1] = false;
        }

        std::pair <int,int> res = reach(i, 0, 0);
        assert(res == dfsReach[i]);
    }

    for (int i = 0 ; i < q ; ++i)
    {
        g1 = G[i];
        int ans = 0;

        for (int fromMAX = 0 ; fromMAX < 2 ; ++fromMAX)
        {
            for (int j = 0 ; j <= g1 ; ++j)
            {
                std::pair <int,int> res = dfsCycle(p, fromMAX, j);
                if (res.first == 1) ans += cnt[j][fromMAX];
            }
        }

        answer(ans);
    }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3924 KB Output is correct
2 Correct 3 ms 3924 KB Output is correct
3 Correct 3 ms 3924 KB Output is correct
4 Correct 2 ms 3836 KB Output is correct
5 Correct 2 ms 3796 KB Output is correct
6 Correct 7 ms 4052 KB Output is correct
7 Correct 2 ms 3796 KB Output is correct
8 Correct 3 ms 3836 KB Output is correct
9 Correct 5 ms 4196 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3924 KB Output is correct
2 Correct 3 ms 3924 KB Output is correct
3 Correct 3 ms 3924 KB Output is correct
4 Correct 2 ms 3836 KB Output is correct
5 Correct 2 ms 3796 KB Output is correct
6 Correct 7 ms 4052 KB Output is correct
7 Correct 2 ms 3796 KB Output is correct
8 Correct 3 ms 3836 KB Output is correct
9 Correct 5 ms 4196 KB Output is correct
10 Correct 431 ms 3852 KB Output is correct
11 Execution timed out 5046 ms 5388 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3924 KB Output is correct
2 Correct 3 ms 3924 KB Output is correct
3 Correct 3 ms 3924 KB Output is correct
4 Correct 2 ms 3836 KB Output is correct
5 Correct 2 ms 3796 KB Output is correct
6 Correct 7 ms 4052 KB Output is correct
7 Correct 2 ms 3796 KB Output is correct
8 Correct 3 ms 3836 KB Output is correct
9 Correct 5 ms 4196 KB Output is correct
10 Correct 431 ms 3852 KB Output is correct
11 Execution timed out 5046 ms 5388 KB Time limit exceeded
12 Halted 0 ms 0 KB -