oj.uz

답안 #122597

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
122597 2019-06-28T17:09:46 Z CaroLinda 열대 식물원 (Tropical Garden) (IOI11_garden) C++14
49 / 100
 16 ms 10104 KB 
#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.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(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

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5112 KB Output is correct
2 Correct 6 ms 4984 KB Output is correct
3 Correct 6 ms 5084 KB Output is correct
4 Correct 6 ms 5112 KB Output is correct
5 Correct 8 ms 5012 KB Output is correct
6 Correct 7 ms 5112 KB Output is correct
7 Correct 5 ms 5084 KB Output is correct
8 Correct 8 ms 5112 KB Output is correct
9 Correct 8 ms 5112 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5112 KB Output is correct
2 Correct 6 ms 4984 KB Output is correct
3 Correct 6 ms 5084 KB Output is correct
4 Correct 6 ms 5112 KB Output is correct
5 Correct 8 ms 5012 KB Output is correct
6 Correct 7 ms 5112 KB Output is correct
7 Correct 5 ms 5084 KB Output is correct
8 Correct 8 ms 5112 KB Output is correct
9 Correct 8 ms 5112 KB Output is correct
10 Runtime error 16 ms 10104 KB Execution killed with signal 8 (could be triggered by violating memory limits)
11 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5112 KB Output is correct
2 Correct 6 ms 4984 KB Output is correct
3 Correct 6 ms 5084 KB Output is correct
4 Correct 6 ms 5112 KB Output is correct
5 Correct 8 ms 5012 KB Output is correct
6 Correct 7 ms 5112 KB Output is correct
7 Correct 5 ms 5084 KB Output is correct
8 Correct 8 ms 5112 KB Output is correct
9 Correct 8 ms 5112 KB Output is correct
10 Runtime error 16 ms 10104 KB Execution killed with signal 8 (could be triggered by violating memory limits)
11 Halted 0 ms 0 KB -