Submission #1104578

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104578		tammaidai	Tropical Garden (IOI11_garden)	C++17	69 / 100	5070 ms	78516 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include<bits/stdc++.h>
using namespace std;
pair<int,int> adj[150010][2];
// vector<pair<int,int>> rev[150010][2];
pair<int,int> jump[150010][31][2];
int dg[150010];
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
  memset(adj,-1,sizeof(adj));
  for(int i = 0;i<M;i++){
    int u = R[i][0];
    int v = R[i][1];
    // cout << u << ' ';
    // cout << v << '\n';
    dg[u]++;
    dg[v]++;
    if(dg[u]==1){
      // adj[u][0] = adj[u][1] = {v,dg[v]==1};
      jump[u][0][0] = jump[u][0][1] = {v,dg[v]==1};
    }
    else if(dg[u]==2){
      // adj[u][1] = {v,dg[v]==1};
      jump[u][0][1] = {v,dg[v]==1};
    }
    if(dg[v]==1){
      jump[v][0][0] = jump[v][0][1] = {u,dg[u]==1};
      // adj[v][0] = adj[u][1] = {u,dg[u]==1};
    }
    else if(dg[v]==2){
      jump[v][0][1] = {u,dg[u]==1};
      // adj[v][1] = {u,dg[u]==1};
    }
  }
  // for(int i = 0;i<N;i++){
  //   cout << jump[i][0][0].first<<' '<< jump[i][0][0].second<<' ' << jump[i][0][1].first<<' '<< jump[i][0][1].second<<'\n';
  // }
  // for(int i = 0;i<N;i++){
  //   rev[adj[i][0].first][adj[i][0].second].push_back({i,0});
  //   rev[adj[i][1].first][adj[i][1].second].push_back({i,1});
  // }
  for(int i = 1;i<30;i++){
    for(int j=0;j<N;j++){
      jump[j][i][0]=jump[jump[j][i-1][0].first][i-1][jump[j][i-1][0].second];
      jump[j][i][1]=jump[jump[j][i-1][1].first][i-1][jump[j][i-1][1].second];
    }
  }
  // cout << jump[0][0][0].first << ' ' << jump[0][0][0].second<<'\n';
  for(int i = 0;i<Q;i++){
    int ans = 0;
    for(int j = 0;j<N;j++){
      pair<int,int> a = {j,0};
      for(int k = 0;k<30;k++){
        if((1<<k)&G[i]){
          a = jump[a.first][k][a.second];
        }
      }
      if(a.first == P){
        ans++;
      }
    }
    answer(ans);
  }

}

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