oj.uz

Submission #116555

# Submission time Handle Problem Language Result Execution time Memory
116555 2019-06-12T22:58:52 Z dragonslayerit Tropical Garden (IOI11_garden) C++14
49 / 100
 73 ms 23672 KB 
#include "garden.h"
#include "gardenlib.h"
#include <vector>
#include <queue>
#include <cstdio>

const int INF=1e9+7;

static std::vector<int> adj[100005];
static int to[200005];
static std::vector<int> from[200005];

static int dist[2][200005];

static void bfs(int start,int* dist){
  std::queue<int> q;
  q.push(start);
  while(!q.empty()){
    int node=q.front();
    q.pop();
    for(int child:from[node]){
      if(!dist[child]){
	dist[child]=dist[node]+1;
	q.push(child);
      }
    }
  }
}

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++){
    printf("adj[%d][0]=%d\n",i,adj[i][0]);
    if(adj[i].size()>1){
      printf("adj[%d][1]=%d\n",i,adj[i][1]);
    }
  }
  */
  for(int i=0;i<N;i++){
    to[i<<1]=(adj[i][0]<<1)|(i==adj[adj[i][0]][0]);
    if(adj[i].size()>1){
      to[i<<1|1]=(adj[i][1]<<1)|(i==adj[adj[i][1]][0]);
    }else{
      to[i<<1|1]=to[i<<1];
    }
  }
  /*
  for(int i=0;i<N*2;i++){
    fprintf(stderr,"to[%d,%d]=%d,%d\n",i>>1,i&1,to[i]>>1,to[i]&1);
  }
  */
  for(int i=0;i<N*2;i++){
    from[to[i]].push_back(i);
  }
  bfs(P<<1,dist[0]);
  bfs(P<<1|1,dist[1]);
  int cycle[2];
  cycle[0]=dist[0][P<<1]?dist[0][P<<1]:INF;
  cycle[1]=dist[1][P<<1|1]?dist[1][P<<1|1]:INF;
  /*
  for(int i=0;i<N*2;i++){
    fprintf(stderr,"dist[%d,%d]=%d\n",i>>1,i&1,dist[0][i]);
  }
  */
  for(int q=0; q<Q; q++){
    int K=G[q];
    int ans=0;
    for(int i=0;i<N;i++){
      /*
      int x=i<<1;
      for(int k=0;k<K;k++){
	x=to[x];
      }
      if((x>>1)==P){
	ans++;
      }
      */
      
      if(dist[0][i<<1]) ans+=(K>=dist[0][i<<1]&&(K-dist[0][i<<1])%cycle[0]==0);
      if(dist[1][i<<1]) ans+=(K>=dist[1][i<<1]&&(K-dist[1][i<<1])%cycle[1]==0);
    }
    answer(ans);
  }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 7516 KB Output is correct
2 Correct 11 ms 7544 KB Output is correct
3 Correct 8 ms 7544 KB Output is correct
4 Correct 10 ms 7412 KB Output is correct
5 Correct 8 ms 7428 KB Output is correct
6 Correct 11 ms 7476 KB Output is correct
7 Correct 11 ms 7444 KB Output is correct
8 Correct 9 ms 7544 KB Output is correct
9 Correct 14 ms 7592 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 7516 KB Output is correct
2 Correct 11 ms 7544 KB Output is correct
3 Correct 8 ms 7544 KB Output is correct
4 Correct 10 ms 7412 KB Output is correct
5 Correct 8 ms 7428 KB Output is correct
6 Correct 11 ms 7476 KB Output is correct
7 Correct 11 ms 7444 KB Output is correct
8 Correct 9 ms 7544 KB Output is correct
9 Correct 14 ms 7592 KB Output is correct
10 Correct 8 ms 7416 KB Output is correct
11 Correct 21 ms 9464 KB Output is correct
12 Correct 42 ms 10908 KB Output is correct
13 Correct 57 ms 18128 KB Output is correct
14 Runtime error 73 ms 23672 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 7516 KB Output is correct
2 Correct 11 ms 7544 KB Output is correct
3 Correct 8 ms 7544 KB Output is correct
4 Correct 10 ms 7412 KB Output is correct
5 Correct 8 ms 7428 KB Output is correct
6 Correct 11 ms 7476 KB Output is correct
7 Correct 11 ms 7444 KB Output is correct
8 Correct 9 ms 7544 KB Output is correct
9 Correct 14 ms 7592 KB Output is correct
10 Correct 8 ms 7416 KB Output is correct
11 Correct 21 ms 9464 KB Output is correct
12 Correct 42 ms 10908 KB Output is correct
13 Correct 57 ms 18128 KB Output is correct
14 Runtime error 73 ms 23672 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -