oj.uz

Submission #1104761

# Submission time Handle Problem Language Result Execution time Memory
1104761 2024-10-24T10:34:06 Z sweed Tropical Garden (IOI11_garden) C++14
69 / 100
 5000 ms 157160 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(1e9)+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]) 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);
      if(u==p or u==p+n) ans++;
    }
    answer(ans);
  }
  
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 24912 KB Output is correct
2 Correct 6 ms 24912 KB Output is correct
3 Correct 6 ms 25168 KB Output is correct
4 Correct 7 ms 24912 KB Output is correct
5 Correct 5 ms 25072 KB Output is correct
6 Correct 6 ms 25180 KB Output is correct
7 Correct 4 ms 24912 KB Output is correct
8 Correct 6 ms 25168 KB Output is correct
9 Correct 6 ms 24912 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 24912 KB Output is correct
2 Correct 6 ms 24912 KB Output is correct
3 Correct 6 ms 25168 KB Output is correct
4 Correct 7 ms 24912 KB Output is correct
5 Correct 5 ms 25072 KB Output is correct
6 Correct 6 ms 25180 KB Output is correct
7 Correct 4 ms 24912 KB Output is correct
8 Correct 6 ms 25168 KB Output is correct
9 Correct 6 ms 24912 KB Output is correct
10 Correct 5 ms 24912 KB Output is correct
11 Correct 18 ms 43604 KB Output is correct
12 Correct 34 ms 59216 KB Output is correct
13 Correct 62 ms 100540 KB Output is correct
14 Correct 116 ms 144052 KB Output is correct
15 Correct 105 ms 145224 KB Output is correct
16 Correct 71 ms 105828 KB Output is correct
17 Correct 62 ms 92744 KB Output is correct
18 Correct 29 ms 59216 KB Output is correct
19 Correct 107 ms 143944 KB Output is correct
20 Correct 120 ms 145236 KB Output is correct
21 Correct 92 ms 105800 KB Output is correct
22 Correct 80 ms 92744 KB Output is correct
23 Correct 151 ms 157160 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 24912 KB Output is correct
2 Correct 6 ms 24912 KB Output is correct
3 Correct 6 ms 25168 KB Output is correct
4 Correct 7 ms 24912 KB Output is correct
5 Correct 5 ms 25072 KB Output is correct
6 Correct 6 ms 25180 KB Output is correct
7 Correct 4 ms 24912 KB Output is correct
8 Correct 6 ms 25168 KB Output is correct
9 Correct 6 ms 24912 KB Output is correct
10 Correct 5 ms 24912 KB Output is correct
11 Correct 18 ms 43604 KB Output is correct
12 Correct 34 ms 59216 KB Output is correct
13 Correct 62 ms 100540 KB Output is correct
14 Correct 116 ms 144052 KB Output is correct
15 Correct 105 ms 145224 KB Output is correct
16 Correct 71 ms 105828 KB Output is correct
17 Correct 62 ms 92744 KB Output is correct
18 Correct 29 ms 59216 KB Output is correct
19 Correct 107 ms 143944 KB Output is correct
20 Correct 120 ms 145236 KB Output is correct
21 Correct 92 ms 105800 KB Output is correct
22 Correct 80 ms 92744 KB Output is correct
23 Correct 151 ms 157160 KB Output is correct
24 Correct 9 ms 24912 KB Output is correct
25 Correct 2753 ms 43800 KB Output is correct
26 Execution timed out 5050 ms 59472 KB Time limit exceeded
27 Halted 0 ms 0 KB -