Submission #797522

#	Time	Username	Problem	Language	Result	Execution time	Memory
797522		farhan132	Tropical Garden (IOI11_garden)	C++17	100 / 100	2389 ms	24528 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef int ll;
typedef double dd;
typedef pair<ll , ll> ii;
typedef tuple < ll,  ll, ll > tp;
 
#define ff first
#define ss second
#define pb push_back
#define in insert
#define mem(a , b) memset(a, b ,sizeof(a))


const ll N = 2e5 + 5;
const ll INF = 1e9 + 3;

vector < ll > v[N];

ii nxt(ll node, ll t){
  if(v[node].size() == 1 && t > 0) t = 0; 
  return {v[node][t] , ((node == v[v[node][t]][0] && v[v[node][t]].size() > 1) ? 1 : 0)};
}
ll vis[N][2];
ll dp[N][2][2], P;

ll go(ll node, ll t, ll tar){
  if(make_pair(node, t) == make_pair(P, tar)){
    return dp[node][t][tar] = 0;
  }
  if(dp[node][t][tar] != -1){
    return dp[node][t][tar];
  }
  vis[node][t] = 1;
  auto [n1, t1] = nxt(node, t);
  if(vis[n1][t1] == 1){
    vis[node][t] = 2;
    return dp[node][t][tar] = INF;
  }
  dp[node][t][tar] = min(INF, go(n1, t1, tar) + 1);
  vis[node][t] = 2;
  return dp[node][t][tar];
}

void count_routes(int n, int m, int _P, int R[][2], int Q, int G[]){

  P = _P;
  
  for(ll i = 0; i < m; i++){
    v[R[i][0]].pb(R[i][1]);
    v[R[i][1]].pb(R[i][0]);
  }

  ll cycle[2] = {0, 0}; 
  mem(vis, 0); 
  ii cur = {P, 0};
  while(true){
    vis[cur.ff][cur.ss] = 1;
    //cout << cur.ff << ' ' << cur.ss << '\n';
    ii NXT = nxt(cur.ff, cur.ss);
    cycle[0]++;
    if(NXT == make_pair(P, 0)){
      break;
    }
    if(vis[NXT.ff][NXT.ss]){
      cycle[0] = INF;
      break;
    }
    cur = NXT;
  }
  if(v[P].size() == 1){
      cycle[1] = INF; 
  }else{
    mem(vis, 0); 
    cur = {P, 1};
    while(true){
      vis[cur.ff][cur.ss] = 1;
      ii NXT = nxt(cur.ff, cur.ss);
      cycle[1]++;
      if(NXT == make_pair(P, 1)){
        break;
      }
      if(vis[NXT.ff][NXT.ss]){
        cycle[1] = INF;
        break;
      }
      cur = NXT;
    }
  }
  //cout << cycle[0] << ' ' << cycle[1] << '\n';
  mem(dp, -1);
  for(ll tar = 0; tar < 2; tar++){
    mem(vis, 0);
    for(ll i = 0; i < n; i++){
      for(ll j = 0; j < 1; j++){
        go(i, j, tar);
      }
    }
  }
  for(ll j = 0; j < Q; j++){
    ll ans = 0;
    for(ll tar = 0; tar < 2; tar++){
      for(ll i = 0; i < n; i++){
        if(dp[i][0][tar] <= G[j] && (G[j] - dp[i][0][tar]) % cycle[tar] == 0){
         ans++;
        }
      }
    }
    answer(ans);
  }

  return;
}

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