oj.uz

답안 #1113898

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1113898 2024-11-17T18:42:07 Z yarengkm 열대 식물원 (Tropical Garden) (IOI11_garden) C++17
0 / 100
 14 ms 14928 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 i=0;i<N;i++){
      pi p={i,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
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 14 ms 14928 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 14 ms 14928 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 14 ms 14928 KB Output isn't correct
2 Halted 0 ms 0 KB -