제출 #347849

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
347849		idk321	열대 식물원 (Tropical Garden) (IOI11_garden)	C++11	0 / 100	7 ms	6252 KiB

garden

#include "garden.h"
#include "gardenlib.h"

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 150001;
vector<int> adj[N];
int cNum = 1;
int cSize[N][2];
int best[N][2];
int dist[N][2][2];
vector<array<int, 2>> st;
int onSt[N][2];
int p;

void dfs(int node, int type)
{
    st.push_back({node, type});
    onSt[node][type] = 1;
    array<int, 2> next = {-1, -1};
    int other = -1;
    int eVal = -1;
    if (type == 0)
    {
        other = adj[node][0];
        eVal = best[node][0];
    } else
    {
        other = adj[node][1];
        eVal = best[node][1];
    }

    if (best[other][0] == eVal && best[other][1] != 0)
    {
        next = {other, 1};
    } else
    {
        next = {other, 0};
    }

    if (cSize[next[0]][next[1]])
    {
        cSize[node][type] = cSize[next[0]][next[1]];
        for (int k = 0; k <= 1; k++)
        {
            if (dist[next[0]][next[1]][k] == -1) dist[node][type][k] = -1;
            else dist[node][type][k] = dist[next[0]][next[1]][k] + 1;
        }
    } else if (onSt[next[0]][next[1]])
    {
        auto it = st.rbegin();
        int siz = 0;
        array<int, 2> good = {-1, -1};
        int cdist = 0;
        //cout << node << " " << type << " " << next[0] << " " << next[1] << endl;
        while (*it != next)
        {
            //cout <<(*it)[0] << " " << (*it)[1] << endl;
            siz++;
            array<int, 2> ar1 = {p, 0};
            array<int, 2> ar2 = {p, 1};
            if (*it == ar1)
            {
                good[0] = cdist;
            }
            if (*it == ar2)
            {
                good[1] = cdist;
            }
            cdist++;
            it++;
        }
        //cout <<(*it)[0] << " " << (*it)[1] << endl;
        siz++;
        //cout << "b " << cdist << endl;
        for (int k = 0; k <= 1; k++)
        {
            if (good[k] != -1)
            {
                dist[node][type][k] = siz - good[k];
            }
        }
        cSize[node][type] = siz;
    } else
    {
        dfs(next[0], next[1]);
        cSize[node][type] = cSize[next[0]][next[1]];
        for (int k = 0; k <= 1; k++)
        {
            if (dist[next[0]][next[1]][k] == -1) dist[node][type][k] = -1;
            else dist[node][type][k] = dist[next[0]][next[1]][k] + 1;
        }
    }

    if (node == p) dist[node][type][type] = 0;
    st.pop_back();
    onSt[node][type] = 0;
}

void count_routes(int n, int m, int pa, int R[][2], int Q, int G[])
{

    p = pa;
  for (int i = 0; i < m; i++)
  {
    for (int j = 0; j <= 1; j++)
    {
        if (best[R[i][j]][0] == 0) best[R[i][j]][0] = i + 1;
        else if (best[R[i][j]][1] == 0) best[R[i][j]][1] = i + 1;
    }
    adj[R[i][0]].push_back(R[i][1]);
    adj[R[i][1]].push_back(R[i][0]);
  }

  for (int i = 0; i < N; i++)
  {
        for (int j = 0; j <= 1; j++) for (int l = 0; l <= 1; l++) dist[i][j][l] = -1;
    }


    for (int i = 0; i < n; i++)
    {
        if (!cSize[i][0]) dfs(i, 0);
    }



  for(int i=0; i<Q; i++)
  {
    int sum = 0;
    int cdist = G[i];
    for (int j = 0; j < n; j++)
    {
        if (i == 0) cout << "a " << cSize[j][0]<< " " << dist[j][0][0] << " " << dist[j][0][1] << " " << j <<  endl;
        for (int k = 0; k <= 1; k++)
        {
            if (dist[j][0][k] != -1)
            {
                if (dist[j][0][k] == cdist) sum++;
                else if (cSize[p][k] && cdist > dist[j][0][k] && dist[j][0][k] % cSize[j][0] == cdist % cSize[j][0])
                {
                    sum++;
                }
            }
        }
    }
      answer(sum);
  }
}

/*
5 4 3
0 1
1 2
2 3
3 4
20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1

*/

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