Submission #122634

#	Time	Username	Problem	Language	Result	Execution time	Memory
122634		CaroLinda	Tropical Garden (IOI11_garden)	C++14	49 / 100	53 ms	11000 KiB

garden

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

#define lp(i,a,b) for(int i=a;i<b;i++)
#define pii pair<int,int>
#define ff first
#define ss second

const int MAXN = 15e4+10;
const int MAXM = 15e4+10 ;
const int MAXQ = 2005 ;
const int inf=1e9+10 ;

using namespace std;

int p ;
pii best[MAXN], secBest[MAXN] , dp[MAXN][2] ;

void inc(int i, int j)
{
    if(dp[i][j].ss != -1)
    dp[i][j].ff ++ ;
}

pii calcDp(int i, int j)
{
  if(i==p) return pii(0,j) ;

  if(dp[i][j].ff == -2 ) return dp[i][j]= pii(inf,-1) ;

  if(dp[i][j].ff!=-1) return dp[i][j] ;

  dp[i][j].ff = -2;

  if(j==0)
    dp[i][j] = calcDp(best[i].ff, best[i].ss) ;

  else dp[i][j] = calcDp(secBest[i].ff, secBest[i].ss) ;

  inc(i,j) ;

  return dp[i][j] ;

}

void count_routes(int n , int m , int P, int r[][2] , int q, int g[])
{
  p=P ;

lp(i,0,MAXN)
  best[i] = secBest[i] = pii(-1,0) ;
lp(i,0,MAXN)
lp(j,0,2) dp[i][j] = pii(-1,-1) ;

lp(i,0,m)
  lp(j,0,2)
  {
    int a = r[i][j] , b = r[i][!j] ;
    if(best[a].ff == -1){
      best[a].ff = b ;
      if( best[b].ff == -1 || best[b].ff == a )
        best[a].ss = 1 ;
    }
    else if(secBest[a].ff == -1)
    {
      secBest[a].ff = b ;
      if( best[b].ff == -1 || best[b].ff == a )
        secBest[a].ss = 1 ;
    }
  }

lp(i,0,n)
  if(secBest[i].ff == -1)
    secBest[i] = best[i] ;

 lp(i,0,n)
  lp(j,0,2)
    if(dp[i][j].ff == -1 && best[i].ff != -1 )
      dp[i][j] = calcDp(i,j) ;

dp[p][0] = calcDp(best[p].ff, best[p].ss) ;
inc(p,0) ;
dp[p][1] = calcDp(secBest[p].ff, secBest[p].ss) ;
inc(p,1) ;

int dist[3] = {dp[p][0].ff , dp[p][1].ff , dp[p][0].ff+dp[p][1].ff} ;
int edge[2] = {dp[p][0].ss , dp[p][1].ss} ;

lp(i,0,q)
{
    int ans = 0 ;
    lp(j,0,n)
    {
        int k = dp[j][0].ss , temp=dp[j][0].ff;
        if(k == -1) continue ;

        int forNow = g[i] - temp ;

        if(forNow == 0) ans ++ ;
        if(forNow<=0 || edge[k]==-1) continue ;

        if(edge[k] == k && forNow%dist[k] == 0) ans++ ;

        else
        {

            if(edge[!k] == !k && forNow-dist[k] >= 0)
                {if((forNow-dist[k])%dist[!k] == 0) ans ++ ;}

            else if(edge[!k] == k )
            {
                if( forNow%(dist[2]) == 0 ) ans ++ ;
                else if(forNow>=dist[k] && (forNow-dist[k])%(dist[2])==0) ans++ ;
            }
        }
    }
    answer(ans) ;
}

}

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