Submission #899143

#	Time	Username	Problem	Language	Result	Execution time	Memory
899143		KaleemRazaSyed	Tropical Garden (IOI11_garden)	C++17	0 / 100	2 ms	10588 KiB

garden

//#include "gardenlib.h"
#include "garden.h"
#include<bits/stdc++.h>

using namespace std;

#define pb push_back
const int N = 1.5e5+10, inf = 2e9;
int dis[N][2], cycle[N][2];
vector<int> G[2 * N];
bool seen[2 * N][2];
int par[2 * N][2];

bool check(int v, int d)
{
  bool ans = false;
  if(dis[v][0] != inf)
    if(dis[v][0] <= d)
      {
	int x = d - dis[v][0];
	if(x % cycle[v][0] == 0)
	  return true;
      }
  if(dis[v][1] != inf)
    if(dis[v][1] <= d)
      {
	int x = d - dis[v][1];
	if(x % cycle[v][1] == 0)
	  return true;
      }
  return false;
}

void update_cycle(int v, int c)
{
  int d = dis[v][c] + 1;
  while(v != -1)
    {
      //cerr << "Cycle : " << v << ' ' << c << endl;
      cycle[v][c] = d;
      v = par[v][c];
    }
}

void bfs(int v, int n2, int c) // n2 = 2 * n
{

  for(int i = 0; i < n2; i++)
    dis[i][c] = cycle[i][c] = inf, par[i][c] = -1;
  
  queue<int> Q;
  Q.push(v);
  seen[v][c] = true;
  dis[v][c] = 0;
  while(Q.size())
    {
      int ver = Q.front();
      Q.pop();
      for(int u : G[ver])
	{
	  if(u == v) update_cycle(u, c);
	  if(seen[u][c]) continue;
	  Q.push(u);
	  seen[u][c] = true;
	  par[u][c] = ver;
	  dis[u][c] = dis[ver][c] + 1;
	}
    }
}

void count_routes(int n, int m, int e, int edge[][2], int q, int k[])
{
  int cnt[n] = {}, c[n] = {};
  for(int i = 0; i < m ;i++)
    c[edge[i][0]]++, c[edge[i][1]]++;
  for(int i = 0; i < m; i++)
    {
      int u = edge[i][0], v = edge[i][1];
      cnt[u]++, cnt[v]++;
      if(cnt[u] == 1)
	{
	  if((cnt[v] == 1 && c[v] == 1) || (cnt[v] > 1))
	    G[v].pb(u);
	  else
	    G[v + n].pb(u);
	}
      if(cnt[u] == 2)
	{
	  if((cnt[v] == 1 && c[v] == 1) || (cnt[v] > 1))
	    G[v].pb(u + n);
	  else
	    G[v + n].pb(u + n);
	}

       if(cnt[v] == 1)
	{
	  if((cnt[u] == 1 && c[u] == 1) || (cnt[u] > 1))
	    G[u].pb(v);
	  else
	    G[u + n].pb(v);
	}
      if(cnt[v] == 2)
	{
	  if((cnt[u] == 1 && c[u] == 1) || (cnt[u] > 1))
	    G[u].pb(v + n);
	  else
	    G[u + n].pb(v + n);
	}
      
	
    }
 

  bfs(e, 2 * n, 0);
  bfs(e + n, 2 * n, 1);

 
  for(int i = 0; i < q; i++)
    {
      int ans = 0;
      for(int v = 0; v < n; v++)
	ans += check(v, k[i]);
      //answer(ans);
      cout << ans << ' ';
    }
  
}

/*

#define MAX_M  1000000
#define MAX_Q  2000

static int NN, M, P, Q;
static int R[MAX_M][2];
static int g[MAX_Q];

void read_input()
{
  int i;
  scanf("%d %d %d",&NN,&M,&P);
  for(i=0; i<M; i++)
    scanf("%d %d",&R[i][0],&R[i][1]);
  scanf("%d",&Q);
  for(i=0; i<Q; i++)
    scanf("%d",&g[i]);
}

void answer(int x)
{
  printf("%d ", x);
}

int main()
{
  read_input();
  count_routes(NN,M,P,R,Q,g);
  return 0;
}


//*/

Compilation message (stderr)

garden.cpp: In function 'bool check(int, int)':
garden.cpp:16:8: warning: unused variable 'ans' [-Wunused-variable]
   16 |   bool ans = false;
      |        ^~~

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