Submission #469514

#	Time	Username	Problem	Language	Result	Execution time	Memory
469514		alextodoran	Tropical Garden (IOI11_garden)	C++17	100 / 100	2856 ms	31576 KiB

garden

/**
 ____ ____ ____ ____ ____
||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);

    for(int i = 0; i < Q; i++)
    {
        int K = G[i];

        int cnt = 0;
        for(int i = 0; i < N; i++)
        {
            if(distA[i] <= K && (distA[i] - K) % cycleA == 0)
                cnt++;
            if(distB[i] <= K && (distB[i] - K) % cycleB == 0)
                cnt++;
        }

        answer(cnt);
    }
}

• Subtask 1: 49 / 49
• Subtask 2: 20 / 20
• Subtask 3: 31 / 31