oj.uz

Submission #469521

# Submission time Handle Problem Language Result Execution time Memory
469521 2021-09-01T08:44:05 Z alextodoran Tropical Garden (IOI11_garden) C++17
49 / 100
 150 ms 31292 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, 0);
    vector <int> cntB (N, 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
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 1 ms 332 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 2 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
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 1 ms 332 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 2 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 1 ms 332 KB Output is correct
11 Correct 17 ms 4684 KB Output is correct
12 Correct 31 ms 7604 KB Output is correct
13 Correct 65 ms 19008 KB Output is correct
14 Correct 123 ms 24724 KB Output is correct
15 Correct 150 ms 25596 KB Output is correct
16 Correct 107 ms 18080 KB Output is correct
17 Runtime error 108 ms 31292 KB Execution killed with signal 11
18 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 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 2 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 1 ms 332 KB Output is correct
11 Correct 17 ms 4684 KB Output is correct
12 Correct 31 ms 7604 KB Output is correct
13 Correct 65 ms 19008 KB Output is correct
14 Correct 123 ms 24724 KB Output is correct
15 Correct 150 ms 25596 KB Output is correct
16 Correct 107 ms 18080 KB Output is correct
17 Runtime error 108 ms 31292 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -