제출 #388101

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
388101		blue	열대 식물원 (Tropical Garden) (IOI11_garden)	C++17	0 / 100	10 ms	15708 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

const int MAX_N = 150000;
const int MAX_M = 150000;
int M1;

vector<int> in_edge[MAX_N], out_edge[MAX_N];
vector<int> new_edge(2*MAX_M), new_revedge[2*MAX_M];

                //nodes,n_edges, goal, edges,   n_queries, queries
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    //PART 1: BUILD THE NEW FUNCTIONAL GRAPH

    M1 = M;

    for(int e = 0; e < M; e++)
    {
        out_edge[ R[e][0] ].push_back(e);
        in_edge[ R[e][0] ].push_back(e+M);

        in_edge[ R[e][1] ].push_back(e);
        out_edge[ R[e][1] ].push_back(e+M);
    }

    for(int i = 0; i < N; i++)
    {
        sort(out_edge[i].begin(), out_edge[i].end(),
            [] (int x, int y)
            {
                return x % M1 < y % M1;
            }
        );
    }

    // for(int i = 0; i < N; i++)
    // {
    //     cout << i << " -> ";
    //     for(int e: out_edge[i]) cout << e << ' ';
    //     cout << '\n';
    // }


    for(int i = 0; i < N; i++)
    {
        for(int e: in_edge[i])
        {
            if(out_edge[i][0] + M == e || out_edge[i][0] - M == e)
            {
                if(out_edge[i].size() == 1)
                {
                    new_edge[e] = out_edge[i][0];
                    new_revedge[ out_edge[i][0] ].push_back(e);
                }
                else
                {
                    new_edge[e] = out_edge[i][1];
                    new_revedge[ out_edge[i][1] ].push_back(e);
                }
            }
            else
            {
                new_edge[e] = out_edge[i][0];
                new_revedge[ out_edge[i][0] ].push_back(e);
            }
        }
    }

    // for(int e = 0; e < 2*M; e++) cout << new_edge[e] << ' ';
    // cout << '\n';







    //PART 2:

    /*
        Only one of P's in_edges can be on the new graph's central cycle.
    */

    vector<int> ct(2*M, 0);
    int E = in_edge[P][0];

    for(int X = 0; X < 6*M; X++)
    {
        ct[E]++;
        E = new_edge[E];
    }

    int cycle_length = 0;

    vector<bool> cyclic(2*M, 0);
    for(int i = 0; i < 2*M; i++)
    {
        if(ct[i] >= 2)
        {
            cyclic[i] = 1;
            cycle_length++;
        }
    }

    queue<int> tbv;
    queue<int> dist;

    vector<int> res(2*M, 0);
    vector<int> visit(2*M, 0);

    for(int F: in_edge[P])
    {
         // if(F == 8) continue;
        if(cyclic[F]) visit = vector<int>(2*M, 0);

        tbv.push(F);
        visit[F] = 1;
        dist.push(1);

        if(F < M)
        {
            if(F == out_edge[ R[F][0] ][0]) res[1]++;
        }
        else
        {
            if(F == out_edge[ R[F - M][1] ][0]) res[1]++;
        }

        // cout << "adding " << 0 << '\n';

        while(!tbv.empty())
        {
            int f = tbv.front();
            int d = dist.front();

            tbv.pop();
            dist.pop();

            for(int g: new_revedge[f])
            {
                if(visit[g]) continue;
                visit[g] = 1;
                tbv.push(g);
                dist.push(d+1);

                if(g < M)
                {
                    if(g == out_edge[ R[g][0] ][0]) res[d+1]++;
                }
                else
                {
                    if(g == out_edge[ R[g - M][1] ][0]) res[d+1]++;
                }

                // cout << "adding " << d+1 << '\n';
            }
        }
        if(cyclic[F]) visit = vector<int>(2*M, 0);
        // break;
    }

    // for(int i = 0; i < 2*M; i++) cout << i << ": " << res[i] << '\n';

    // cout << cycle_length << '\n';

    for(int q = 0; q < Q; q++) answer(res[ G[q] ] % cycle_length);
}

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