Submission #1066610

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066610		fractlpaca	Tropical Garden (IOI11_garden)	C++17	0 / 100	1 ms	600 KiB

garden

#include "garden.h"
#include "gardenlib.h"

#include <bits/stdc++.h>
#define v vector
#define pii pair<int,int>
#define ll long long
#define pli pair<long long, int>
#define fi first
#define se second

#define SUBTASK 3

using namespace std;


int LIMIT = 29;
int jump_amount(v<v<int>> &jumps, int a, int amount) {
  for (int j=LIMIT; j>=0; j--) {
    if (1<<j <= amount) {
      amount -= 1<<j;
      a = jumps[j][a];
    }
  }
  return a;
}


void dfs(v<v<int>> &adj, int node, int dist, v<int> &dists) {
  if (dists[node]!=-1) return;
  dists[node] = dist;
  for (int nex: adj[node]) {
    dfs(adj, nex, dist+1, dists);
  }
}

//void bfs(v<v<int>> &adj, int node, int dist, v<int> &dists) {
  //queue<pii> q;
  //q.push({node, dist});
  
  //while (q.size()) {
    //pii front = q.front();
    //int cur=front.fi;
    //int dist=front.se;
    //q.pop();
    
    //if (dists[cur]!=-1) continue;
    //dists[cur] = dist;
    
    //for (int nex: adj[cur]) {
      //q.push({nex, dist+1});
    //}
  //}
  
//}


void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
  v<int> first (N, -1);
  v<int> second (N, -1);
  v<int> next (2*N, -1);
  
  // Build first and second choices
  for (int i=0; i<M; i++) {
    int a=R[i][0];
    int b=R[i][1];
    
    if (first[a]==-1) first[a]=b;
    else if (second[a]==-1) second[a]=b;
    
    if (first[b]==-1) first[b]=a;
    else if (second[b]==-1) second[b]=a;
  }
    
  for (int i=0; i<N; i++) {
    if (second[i]==-1) second[i]=first[i];
  }
  
  // Build next
  for (int i=0; i<N; i++) {
    if (first[first[i]]==i)  next[2*i]=first[i]*2+1;
    else next[2*i]=first[i]*2;
    
    if (first[second[i]]==i) next[2*i+1]=second[i]*2+1;
    else next[2*i+1]=second[i]*2;
  }

  
  //for (int i=0; i<N; i++) {
    //cerr<<i<<": ("<<next[2*i]/2<<","<<next[2*i]%2<<") ("<<next[2*i+1]/2<<","<<next[2*i+1]%2<<")"<<endl;
  //}
  
  if (SUBTASK==1) {
  
  assert(Q==1);
  
  int K=G[0];
  int count = 0;
  for (int i=0; i<N; i++) {
    int cur=2*i;
    for (int j=0; j<K; j++) {
      cur = next[cur];
    }
    if (cur/2 == P) count++;
  }
  answer(count);
  return;
  
  }
  
  // SUBTASK 2
  if (SUBTASK==2) {
  
  // Build jump pointers
  v<v<int>> jumps (LIMIT+1, v<int> (2*N, 0));
  jumps[0] = next;
  for (int i=1; i<=LIMIT; i++) {
    for (int j=0; j<2*N; j++) {
      jumps[i][j] = jumps[i-1][jumps[i-1][j]];
    }
  }
  
  //for (int j=0; j<2*N; j++) {
    //cerr<<j<<" ";
  //}cerr<<endl;
  //for (int i=0; i<=3; i++) {
    //for (int j=0; j<2*N; j++) {
      //cerr<<jumps[i][j]<<" ";
    //}cerr<<endl;
  //}
  
  
  
  for (int i=0; i<Q; i++) {
    int K=G[i];
    int count=0;
    
    for (int j=0; j<N; j++) {
      int end = jump_amount(jumps, 2*j, K);
      //cerr<<j<<" jumps "<<K<<" to ("<< end/2<<","<<end%2<<")"<<endl;
      if (end/2 == P) count++;
    }
    
    answer(count);
  }
  return;
  
  }
  
  // SUBTASK 3
  if (SUBTASK==3) {
  
  
  // Find cycle lengths
  int p_cycle0 = 1e9+100;
  int p_cycle1 = 1e9+100;
  
  int cur=2*P;
  for (int i=0; i<2*N; i++) {
    cur=next[cur];
    if (cur==2*P) {
      p_cycle0 = i+1;
      break;
    }
  }
  
  cur=2*P+1;
  for (int i=0; i<2*N; i++) {
    cur=next[cur];
    if (cur==2*P+1) {
      p_cycle1 = i+1;
      break;
    }
  }
  
  // Construct reverse graph
  v<v<int>> adj (2*N, v<int>(0));
  for (int i=0; i<2*N; i++) {
    adj[next[i]].push_back(i);
  }
  
  v<int> dists0 (2*N, -1);
  v<int> dists1 (2*N, -1);
  // Populate dists0/1
  dfs(adj, 2*P, 0, dists0);
  dfs(adj, 2*P+1, 0, dists1);
  
  //cerr<<p_cycle0<<" "<<p_cycle1<<endl;
  
  for (int i=0; i<Q; i++) {
    int K=G[i];
    int count=0;
    for (int j=0; j<N; j++) {
      if ((dists0[2*j]!=-1 && (K-dists0[2*j])%p_cycle0==0)  ||
          (dists1[2*j]!=-1 && (K-dists1[2*j])%p_cycle1==0))
        count++;
    }
    answer(count);
  }
  return;
  
  }
}

• Subtask 1: 0 / 49
• Subtask 2: 0 / 20
• Subtask 3: 0 / 31