Submission #29515

#	Time	Username	Problem	Language	Result	Execution time	Memory
29515		kavun	Tropical Garden (IOI11_garden)	C++14	0 / 100	17 ms	16928 KiB

garden

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

using namespace std;
typedef pair<int,int> ii;
int nfirst,p,q,f1[300010], f2[300010];
vector <ii> adj[200010];
vector <int> tadj[300010],ans, best[200010];
bool mk1[300010], mk2[300010];
int cycle1, cycle2, flag;

inline int complement(int a)
{
  if(a < nfirst)
    return a + nfirst;
  else
    return a - nfirst;
}

void dfs(int v, int d, bool mk[],int f[], int root)
{
  mk[v] = true;
  f[v] = d;
  for(int i = 0; i < tadj[v].size(); i++)
    {
      int u = tadj[v][i];
      if(u == root){if(flag) cycle2 = d+1; else cycle1 = d+1;}
      if(!mk[u])
	dfs(u,d+1,mk,f,root);
    }
}


void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
  nfirst = N;

  for(int i = 0; i < M;i++)
    {
      int u = R[i][0];
      int v = R[i][1];
      if( best[v].size() <= 1 ) best[v].pb( u );
      if( best[u].size() <= 1 ) best[u].pb( v );
    }

    for(int i=0;i<N;i++)
        if( best[i].size() == 1 ) best[i].pb( best[i][0] );

    for(int i = 0; i < N; i++)
      {
	int go = best[i][0];
	int s = (best[go][0] == i);
	if(s)
	  tadj[complement(go)].pb(i);
	else
	  tadj[go].pb(i);
      }
    for(int i = N; i < 2*N; i++)
      {
	int go = best[complement(i)][1];
	int s = (best[go][0] == complement(i));
	if(s)
	  tadj[complement(go)].pb(i);
	else
	  tadj[go].pb(i);
      }

  
  dfs(P,0,mk1,f1,P);
  flag=1;

  for(int i = 0; i < Q; i++)
    {
      int sum = 0;
      for(int v = 0; v < N; v++)      
	{
	  if(!mk1[v]) continue;
	  if(cycle1 && ((G[i] - f1[v]) % cycle1) == 0 && G[i] - f1[i] >= 0)
	    sum++;
	  else 
	    if(G[i] == f1[v])
	      sum++;
	}
      ans.push_back(sum);
    }

  dfs(complement(P),0,mk2,f2,complement(P));

    for(int i = 0; i < Q; i++)
      {
	int sum = 0;
	for(int v = 0; v < N; v++)
	  {
	    if(!mk2[v]) continue;
	    if(cycle2 && ((G[i] - f2[v]) % cycle2) == 0 && G[i] - f2[i] >= 0)
	      sum++;
	    else 
	      if(G[i] == f2[v])
		sum++;
	  }
	ans[i] += sum;
      }

  for(int i = 0;i < Q; i++)
    answer(ans[i]);
}

Compilation message (stderr)

garden.cpp: In function 'void dfs(int, int, bool*, int*, int)':
garden.cpp:26:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < tadj[v].size(); i++)
                  ~~^~~~~~~~~~~~~~~~

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