oj.uz

답안 #1104757

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1104757 2024-10-24T10:28:39 Z sweed 열대 식물원 (Tropical Garden) (IOI11_garden) C++14
49 / 100
 50 ms 101292 KB 
#include "garden.h"
#include "gardenlib.h"
#define pb emplace_back
#include<bits/stdc++.h>
using namespace std;
int up[600005][100];
vector<int>g[300005];
vector<int>g2[600005];
int jp=0;
int g_rev[600005];
void setup(int n)
{
  jp=log2(10000000)+1;
 
  for(int i=0;i<2*n;i++) 
  {
    if(!g2[i].empty()) up[i][0]=g2[i][0];
    else up[i][0] = i;
  }
  for(int i=1;i<jp;i++)
  {
    for(int j=0;j<2*n;j++)
    {
      up[j][i] = up[up[j][i-1]][i-1];
    }
  }
}
int jump(int u,int x)
{
  for(int i=jp-1;i>=0;i--)
  {
    if((x&(1<<i))==1<<i)
    {
      u=up[u][i];
    }
  }
  return u;
}
 
 
void count_routes(int n, int m, int p, int R[][2], int Q, int G[])
{
  
  for(int i=0;i<m;i++)
  {
    if(g[R[i][0]].size()<=2) g[R[i][0]].pb(R[i][1]);
    if(g[R[i][1]].size()<=2) g[R[i][1]].pb(R[i][0]);
  }
  for(int i=0;i<n;i++)
  {
    int v = g[i][0];
    if(i==g[v][0] and g[v].size()!=1) g2[i].pb(v+n);
    else  g2[i].pb(v);
    int vv;
    if(g[i].size()!=1) vv = g[i][1];
    else vv = g[i][0];
 
    if(i==g[vv][0]) g2[i+n].pb(vv+n);
    else  g2[i+n].pb(vv);
  }
  setup(n);
  for(int k=0;k<Q;k++)
  {
    int d = G[k];
    int ans=0;
    for(int i=0;i<n;i++)
    {
      int u=i;
      u = jump(u,d);
      // for(int j=0;j<d;j++)
      // {
      //   u = g2[u][0];
      // }
      if(u==p or u==p+n) ans++;
    }
    answer(ans);
  }
  
 
  // for(int i=0; i<Q; i++)
  // answer(n);
}

Subtask #1
49.0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 24912 KB Output is correct
2 Correct 5 ms 24912 KB Output is correct
3 Correct 4 ms 24912 KB Output is correct
4 Correct 4 ms 25076 KB Output is correct
5 Correct 4 ms 24912 KB Output is correct
6 Correct 5 ms 25168 KB Output is correct
7 Correct 4 ms 25028 KB Output is correct
8 Correct 4 ms 25168 KB Output is correct
9 Correct 5 ms 25164 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 24912 KB Output is correct
2 Correct 5 ms 24912 KB Output is correct
3 Correct 4 ms 24912 KB Output is correct
4 Correct 4 ms 25076 KB Output is correct
5 Correct 4 ms 24912 KB Output is correct
6 Correct 5 ms 25168 KB Output is correct
7 Correct 4 ms 25028 KB Output is correct
8 Correct 4 ms 25168 KB Output is correct
9 Correct 5 ms 25164 KB Output is correct
10 Correct 4 ms 24912 KB Output is correct
11 Correct 15 ms 43600 KB Output is correct
12 Correct 31 ms 59488 KB Output is correct
13 Incorrect 50 ms 101292 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 24912 KB Output is correct
2 Correct 5 ms 24912 KB Output is correct
3 Correct 4 ms 24912 KB Output is correct
4 Correct 4 ms 25076 KB Output is correct
5 Correct 4 ms 24912 KB Output is correct
6 Correct 5 ms 25168 KB Output is correct
7 Correct 4 ms 25028 KB Output is correct
8 Correct 4 ms 25168 KB Output is correct
9 Correct 5 ms 25164 KB Output is correct
10 Correct 4 ms 24912 KB Output is correct
11 Correct 15 ms 43600 KB Output is correct
12 Correct 31 ms 59488 KB Output is correct
13 Incorrect 50 ms 101292 KB Output isn't correct
14 Halted 0 ms 0 KB -