oj.uz

Submission #1113900

# Submission time Handle Problem Language Result Execution time Memory
1113900 2024-11-17T18:45:44 Z yarengkm Tropical Garden (IOI11_garden) C++17
69 / 100
 5000 ms 105300 KB 
#include "garden.h"
#include "gardenlib.h"
#include<bits/stdc++.h>
#define pb push_back
#define pi pair<int,int>
#define fi first
#define se second 
using namespace std;
const int maxn=2*1e5;
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
  vector<int>adj[maxn];
  vector<pair<int,int>>c1[maxn];
  vector<pair<int,int>>c2[maxn];
  for(int i=0;i<M;i++){
    adj[R[i][0]].push_back(R[i][1]);
    adj[R[i][1]].push_back(R[i][0]);
  }
  for(int i=0;i<N;i++){
    pi p={0,0};
    p.fi=adj[i][0];
    if(adj[p.fi][0]==i)p.se=1;
    c1[i].pb(p);
    if(adj[i].size()>1){
      p.fi=adj[i][1];
      if(adj[p.fi][0]==i)p.se=1;
      else p.se=0;
    }
    c2[i].pb(p);
  }
  for(int i=1;i<=ceil(log2(1e9));i++){
    for(int j=0;j<N;j++){
      pair<int,int>p=c1[j][i-1];
      if(p.se==0)p=c1[p.fi][i-1];
      else p=c2[p.fi][i-1];
      c1[j].pb(p);
      p=c2[j][i-1];
      if(p.se==0)p=c1[p.fi][i-1];
      else p=c2[p.fi][i-1];
      c2[j].pb(p);
    }
  }
  for(int i=0; i<Q; i++){
    int k=G[i];
    int ans=0;
    for(int m=0;m<N;m++){
      pi p={m,0};
      int cur=0;
      k=G[i];
      for(int j=ceil(log2(1e9));j>=0;j--){
        if(k>=(1<<j)){
          if(cur==0)p=c1[p.fi][j];
          else p=c2[p.fi][j];
          cur=p.se;
          k-=(1<<j);
        }
      }
      if(p.fi==P)ans++;
    }
    answer(ans);
  }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14928 KB Output is correct
2 Correct 15 ms 14928 KB Output is correct
3 Correct 16 ms 14928 KB Output is correct
4 Correct 13 ms 14552 KB Output is correct
5 Correct 13 ms 14416 KB Output is correct
6 Correct 14 ms 15024 KB Output is correct
7 Correct 12 ms 14416 KB Output is correct
8 Correct 13 ms 14908 KB Output is correct
9 Correct 20 ms 15440 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14928 KB Output is correct
2 Correct 15 ms 14928 KB Output is correct
3 Correct 16 ms 14928 KB Output is correct
4 Correct 13 ms 14552 KB Output is correct
5 Correct 13 ms 14416 KB Output is correct
6 Correct 14 ms 15024 KB Output is correct
7 Correct 12 ms 14416 KB Output is correct
8 Correct 13 ms 14908 KB Output is correct
9 Correct 20 ms 15440 KB Output is correct
10 Correct 13 ms 14416 KB Output is correct
11 Correct 49 ms 29660 KB Output is correct
12 Correct 78 ms 38988 KB Output is correct
13 Correct 191 ms 66888 KB Output is correct
14 Correct 263 ms 96584 KB Output is correct
15 Correct 307 ms 97748 KB Output is correct
16 Correct 211 ms 71752 KB Output is correct
17 Correct 159 ms 63172 KB Output is correct
18 Correct 78 ms 38984 KB Output is correct
19 Correct 269 ms 96572 KB Output is correct
20 Correct 272 ms 97728 KB Output is correct
21 Correct 198 ms 70224 KB Output is correct
22 Correct 175 ms 63048 KB Output is correct
23 Correct 408 ms 105300 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14928 KB Output is correct
2 Correct 15 ms 14928 KB Output is correct
3 Correct 16 ms 14928 KB Output is correct
4 Correct 13 ms 14552 KB Output is correct
5 Correct 13 ms 14416 KB Output is correct
6 Correct 14 ms 15024 KB Output is correct
7 Correct 12 ms 14416 KB Output is correct
8 Correct 13 ms 14908 KB Output is correct
9 Correct 20 ms 15440 KB Output is correct
10 Correct 13 ms 14416 KB Output is correct
11 Correct 49 ms 29660 KB Output is correct
12 Correct 78 ms 38988 KB Output is correct
13 Correct 191 ms 66888 KB Output is correct
14 Correct 263 ms 96584 KB Output is correct
15 Correct 307 ms 97748 KB Output is correct
16 Correct 211 ms 71752 KB Output is correct
17 Correct 159 ms 63172 KB Output is correct
18 Correct 78 ms 38984 KB Output is correct
19 Correct 269 ms 96572 KB Output is correct
20 Correct 272 ms 97728 KB Output is correct
21 Correct 198 ms 70224 KB Output is correct
22 Correct 175 ms 63048 KB Output is correct
23 Correct 408 ms 105300 KB Output is correct
24 Correct 23 ms 14628 KB Output is correct
25 Execution timed out 5075 ms 30052 KB Time limit exceeded
26 Halted 0 ms 0 KB -