oj.uz

Submission #1104757

# Submission time Handle Problem Language Result Execution time Memory
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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -