Submission #347837

#	Time	Username	Problem	Language	Result	Execution time	Memory
347837		idk321	Tropical Garden (IOI11_garden)	C++11	0 / 100	5 ms	5100 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];
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]];
        if (dist[next[0]][next[1]] == -1) dist[node][type] = -1;
        else dist[node][type] = dist[next[0]][next[1]] + 1;
    } else if (onSt[next[0]][next[1]])
    {
        auto it = st.rbegin();
        int siz = 0;
        int good = -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 || *it == ar2)
            {
                good = cdist;
            }
            cdist++;
            it++;
        }
        //cout <<(*it)[0] << " " << (*it)[1] << endl;
        siz++;
        //cout << "b " << cdist << endl;
        if (good != -1)
        {
            dist[node][type] = siz - good;
        }
        cSize[node][type] = siz;
    } else
    {
        dfs(next[0], next[1]);
        cSize[node][type] = cSize[next[0]][next[1]];
        if (dist[next[0]][next[1]] == -1) dist[node][type] = -1;
        else dist[node][type] = dist[next[0]][next[1]] + 1;
    }

    if (node == p) dist[node][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++) dist[i][j] = -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++)
    {
        //cout << "a " << cSize[j][0]<< " " << dist[j][0] << " " << j <<  endl;
        if (dist[j][0] != -1)
        {
            if (dist[j][0] == cdist) sum++;
            else if (dist[j][0] != -1 && cSize[j][0] && cdist > dist[j][0] && dist[j][0] % cSize[j][0] == cdist % cSize[j][0])
            {
                sum++;
            }
        }
    }
      answer(sum);
  }
}

/*
4 3 3
0 1
1 2
2 3
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