oj.uz

Submission #1113875

# Submission time Handle Problem Language Result Execution time Memory
1113875 2024-11-17T16:44:38 Z yarengkm Tropical Garden (IOI11_garden) C++17
0 / 100
 4 ms 15440 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;
vector<int>adj[maxn];
vector<pair<int,int>>c1[maxn];
vector<pair<int,int>>c2[maxn];
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
  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 i=0;i<N;i++){
      pi p={i,0};
      int cur=0;
      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
0 / 49.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 15440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 15440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 15440 KB Output isn't correct
2 Halted 0 ms 0 KB -