oj.uz

Submission #469523

# Submission time Handle Problem Language Result Execution time Memory
469523 2021-09-01T08:45:04 Z alextodoran Tropical Garden (IOI11_garden) C++17
0 / 100
 1 ms 460 KB 
/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>
#include "garden.h"

using namespace std;

typedef long long ll;

void answer (int x);

void count_routes (int N, int M, int P, int R[][2], int Q, int G[])
{
    vector <vector <int>> adj (N);
    for(int i = 0; i < M; i++)
    {
        adj[R[i][0]].push_back(R[i][1]);
        adj[R[i][1]].push_back(R[i][0]);
    }

    vector <int> edge (N * 2);
    for(int u = 0; u < N; u++)
    {
        edge[u] = adj[u][0];
        if(adj[edge[u]][0] == u)
            edge[u] += N;
    }
    for(int u = 0; u < N; u++)
    {
        if((int) adj[u].size() >= 2)
            edge[N + u] = adj[u][1];
        else
            edge[N + u] = adj[u][0];

        if(adj[edge[N + u]][0] == u)
            edge[N + u] += N;
    }

    vector <vector <int>> rev (N * 2);
    for(int u = 0; u < N * 2; u++)
        rev[edge[u]].push_back(u);

    function <void (int, vector <int> &, int&)> bfs = [&] (int start, vector <int> &dist, int &cycle)
    {
        dist = vector <int> (N * 2, INT_MAX);

        queue <int> q;

        q.push(start);
        dist[start] = 0;

        while(q.empty() == false)
        {
            int u = q.front();
            q.pop();

            for(int v : rev[u])
                if(dist[v] == INT_MAX)
                {
                    dist[v] = dist[u] + 1;
                    q.push(v);
                }
        }

        cycle = 0;
        vector <bool> seen (N * 2, false);
        int u = start;
        while(seen[u] == false)
        {
            cycle++;
            seen[u] = true;
            u = edge[u];
        }

        if(u != start || cycle == 1)
            cycle = INT_MAX;
    };

    vector <int> distA, distB;
    int cycleA, cycleB;

    bfs(P, distA, cycleA);
    bfs(N + P, distB, cycleB);

    vector <int> vecA, vecB;
    for(int i = 0; i < N; i++)
    {
        if(distA[i] != INT_MAX)
            vecA.push_back(distA[i]);
        if(distB[i] != INT_MAX)
            vecB.push_back(distB[i]);
    }

    sort(vecA.begin(), vecA.end(), greater <int> ());
    sort(vecB.begin(), vecB.end(), greater <int> ());

    vector <int> perm (Q);
    for(int i = 0; i < Q; i++)
        perm[i] = i;
    sort(perm.begin(), perm.end(),
         [&] (const int &i, const int &j)
         {
             return G[i] < G[j];
         });

    vector <int> ans (Q);

    vector <int> cntA (N * 2, 0);
    vector <int> cntB (N * 2, 0);

    for(int x = 0; x < Q; x++)
    {
        int i = perm[x];

        while(vecA.empty() == false && vecA.back() <= G[i])
        {
            cntA[vecA.back() % cycleA]++;
            vecA.pop_back();
        }
        while(vecB.empty() == false && vecB.back() <= G[i])
        {
            cntB[vecB.back() % cycleB]++;
            vecB.pop_back();
        }

        ans[i] = cntA[G[i] % cycleA] + cntB[G[i] % cycleB];
    }

    for(int i = 0; i < Q; i++)
        answer(ans[i]);
}

Subtask #1
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Incorrect 0 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Incorrect 0 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Incorrect 0 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -