oj.uz

Submission #469529

# Submission time Handle Problem Language Result Execution time Memory
469529 2021-09-01T08:59:26 Z alextodoran Tropical Garden (IOI11_garden) C++17
100 / 100
 163 ms 33240 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 u = 0; u < N; u++)
    {
        if(distA[u] != INT_MAX)
            vecA.push_back(distA[u]);
        if(distB[u] != INT_MAX)
            vecB.push_back(distB[u]);
    }

    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();
        }

        if(G[i] % cycleA < N * 2)
            ans[i] += cntA[G[i] % cycleA];
        if(G[i] % cycleB < N * 2)
            ans[i] += cntB[G[i] % cycleB];
    }

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

Subtask #1
49.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 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 3 ms 588 KB Output is correct

Subtask #2
20.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 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 3 ms 588 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 13 ms 4604 KB Output is correct
12 Correct 29 ms 7460 KB Output is correct
13 Correct 63 ms 19164 KB Output is correct
14 Correct 120 ms 25316 KB Output is correct
15 Correct 154 ms 26168 KB Output is correct
16 Correct 111 ms 18308 KB Output is correct
17 Correct 97 ms 15800 KB Output is correct
18 Correct 32 ms 7872 KB Output is correct
19 Correct 112 ms 25816 KB Output is correct
20 Correct 163 ms 26720 KB Output is correct
21 Correct 104 ms 18800 KB Output is correct
22 Correct 92 ms 16408 KB Output is correct
23 Correct 127 ms 28252 KB Output is correct

Subtask #3
31.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 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 3 ms 588 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 13 ms 4604 KB Output is correct
12 Correct 29 ms 7460 KB Output is correct
13 Correct 63 ms 19164 KB Output is correct
14 Correct 120 ms 25316 KB Output is correct
15 Correct 154 ms 26168 KB Output is correct
16 Correct 111 ms 18308 KB Output is correct
17 Correct 97 ms 15800 KB Output is correct
18 Correct 32 ms 7872 KB Output is correct
19 Correct 112 ms 25816 KB Output is correct
20 Correct 163 ms 26720 KB Output is correct
21 Correct 104 ms 18800 KB Output is correct
22 Correct 92 ms 16408 KB Output is correct
23 Correct 127 ms 28252 KB Output is correct
24 Correct 1 ms 332 KB Output is correct
25 Correct 15 ms 4844 KB Output is correct
26 Correct 38 ms 7968 KB Output is correct
27 Correct 65 ms 19680 KB Output is correct
28 Correct 113 ms 25820 KB Output is correct
29 Correct 143 ms 26640 KB Output is correct
30 Correct 106 ms 18796 KB Output is correct
31 Correct 99 ms 16316 KB Output is correct
32 Correct 38 ms 8004 KB Output is correct
33 Correct 114 ms 25796 KB Output is correct
34 Correct 145 ms 26644 KB Output is correct
35 Correct 120 ms 18876 KB Output is correct
36 Correct 110 ms 16504 KB Output is correct
37 Correct 119 ms 28276 KB Output is correct
38 Correct 122 ms 33240 KB Output is correct