oj.uz

답안 #1104758

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1104758 2024-10-24T10:29:01 Z sweed 열대 식물원 (Tropical Garden) (IOI11_garden) C++14
49 / 100
 71 ms 100424 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 4 ms 25160 KB Output is correct
3 Correct 4 ms 24912 KB Output is correct
4 Correct 4 ms 24912 KB Output is correct
5 Correct 4 ms 24912 KB Output is correct
6 Correct 4 ms 25036 KB Output is correct
7 Correct 6 ms 24928 KB Output is correct
8 Correct 4 ms 25168 KB Output is correct
9 Correct 5 ms 24912 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 24912 KB Output is correct
2 Correct 4 ms 25160 KB Output is correct
3 Correct 4 ms 24912 KB Output is correct
4 Correct 4 ms 24912 KB Output is correct
5 Correct 4 ms 24912 KB Output is correct
6 Correct 4 ms 25036 KB Output is correct
7 Correct 6 ms 24928 KB Output is correct
8 Correct 4 ms 25168 KB Output is correct
9 Correct 5 ms 24912 KB Output is correct
10 Correct 4 ms 25168 KB Output is correct
11 Correct 15 ms 43768 KB Output is correct
12 Correct 31 ms 59216 KB Output is correct
13 Incorrect 71 ms 100424 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 4 ms 25160 KB Output is correct
3 Correct 4 ms 24912 KB Output is correct
4 Correct 4 ms 24912 KB Output is correct
5 Correct 4 ms 24912 KB Output is correct
6 Correct 4 ms 25036 KB Output is correct
7 Correct 6 ms 24928 KB Output is correct
8 Correct 4 ms 25168 KB Output is correct
9 Correct 5 ms 24912 KB Output is correct
10 Correct 4 ms 25168 KB Output is correct
11 Correct 15 ms 43768 KB Output is correct
12 Correct 31 ms 59216 KB Output is correct
13 Incorrect 71 ms 100424 KB Output isn't correct
14 Halted 0 ms 0 KB -