oj.uz

Submission #122611

# Submission time Handle Problem Language Result Execution time Memory
122611 2019-06-28T18:59:03 Z CaroLinda Tropical Garden (IOI11_garden) C++14
69 / 100
 1617 ms 11424 KB 
#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 = 15e5+10 ;
const int MAXQ = 2005 ;
const int inf=1e9+10 ;

using namespace std;

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

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) ;
    dp[i][j].ff++ ;
    return dp[i][j] ;
  }

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

}

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

//my calculus
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) ;

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

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)
      dp[i][j] = calcDp(i,j) ;

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

int aux[2] = {dp[p][0].ff , dp[p][1].ff} ;
pii myp = pii(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 ;

        if(g[i] < temp) continue ;
        if(g[i] == temp) {ans++ ; continue ;}

        if(myp == pii(0,1)){
            if( (g[i]-temp)%aux[k] == 0)
                ans ++ ;
        }

        else if (myp == pii(1,0))
        {
            if( (g[i]-temp)%(aux[k]+aux[!k]) == 0 )
                ans ++ ;
            else if( g[i]-temp>=aux[k] )
                if( (g[i]-temp-aux[k])%(aux[k]+aux[!k]) == 0 )
                    ans ++ ;
        }

        else
        {
            int kline = myp.ff;
            if( g[i] - temp >= aux[k] )
                if( (g[i]-temp-aux[k])%aux[kline] == 0)
                    ans ++ ;

        }
    }
    answer(ans) ;
}

}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5084 KB Output is correct
2 Correct 6 ms 4984 KB Output is correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 6 ms 5116 KB Output is correct
5 Correct 7 ms 5084 KB Output is correct
6 Correct 7 ms 5116 KB Output is correct
7 Correct 6 ms 5112 KB Output is correct
8 Correct 6 ms 4984 KB Output is correct
9 Correct 6 ms 5112 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5084 KB Output is correct
2 Correct 6 ms 4984 KB Output is correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 6 ms 5116 KB Output is correct
5 Correct 7 ms 5084 KB Output is correct
6 Correct 7 ms 5116 KB Output is correct
7 Correct 6 ms 5112 KB Output is correct
8 Correct 6 ms 4984 KB Output is correct
9 Correct 6 ms 5112 KB Output is correct
10 Correct 6 ms 5128 KB Output is correct
11 Correct 14 ms 5496 KB Output is correct
12 Correct 21 ms 5752 KB Output is correct
13 Correct 32 ms 11384 KB Output is correct
14 Correct 50 ms 6744 KB Output is correct
15 Correct 54 ms 6776 KB Output is correct
16 Correct 52 ms 6492 KB Output is correct
17 Correct 47 ms 6520 KB Output is correct
18 Correct 22 ms 5624 KB Output is correct
19 Correct 50 ms 6648 KB Output is correct
20 Correct 61 ms 6852 KB Output is correct
21 Correct 48 ms 6520 KB Output is correct
22 Correct 50 ms 6392 KB Output is correct
23 Correct 53 ms 6976 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5084 KB Output is correct
2 Correct 6 ms 4984 KB Output is correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 6 ms 5116 KB Output is correct
5 Correct 7 ms 5084 KB Output is correct
6 Correct 7 ms 5116 KB Output is correct
7 Correct 6 ms 5112 KB Output is correct
8 Correct 6 ms 4984 KB Output is correct
9 Correct 6 ms 5112 KB Output is correct
10 Correct 6 ms 5128 KB Output is correct
11 Correct 14 ms 5496 KB Output is correct
12 Correct 21 ms 5752 KB Output is correct
13 Correct 32 ms 11384 KB Output is correct
14 Correct 50 ms 6744 KB Output is correct
15 Correct 54 ms 6776 KB Output is correct
16 Correct 52 ms 6492 KB Output is correct
17 Correct 47 ms 6520 KB Output is correct
18 Correct 22 ms 5624 KB Output is correct
19 Correct 50 ms 6648 KB Output is correct
20 Correct 61 ms 6852 KB Output is correct
21 Correct 48 ms 6520 KB Output is correct
22 Correct 50 ms 6392 KB Output is correct
23 Correct 53 ms 6976 KB Output is correct
24 Correct 6 ms 5084 KB Output is correct
25 Correct 78 ms 5496 KB Output is correct
26 Correct 79 ms 5752 KB Output is correct
27 Correct 1617 ms 11424 KB Output is correct
28 Correct 999 ms 6740 KB Output is correct
29 Correct 1514 ms 6824 KB Output is correct
30 Correct 1034 ms 6616 KB Output is correct
31 Correct 858 ms 8012 KB Output is correct
32 Correct 106 ms 6240 KB Output is correct
33 Correct 1006 ms 8408 KB Output is correct
34 Correct 1507 ms 8540 KB Output is correct
35 Correct 1101 ms 8216 KB Output is correct
36 Correct 870 ms 8012 KB Output is correct
37 Incorrect 683 ms 8908 KB Output isn't correct