제출 #573189

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

garden

 
#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]);
        else 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 / 49
• Subtask 2: 0 / 20
• Subtask 3: 0 / 31