oj.uz

Submission #1104758

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

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

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

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