Submission #1260572

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260572		julia_08	열대 식물원 (Tropical Garden) (IOI11_garden)	C++20	69 / 100	5097 ms	87364 KiB

garden

#include <bits/stdc++.h>

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

using namespace std;

const int MAXN = 2e5 + 10;

vector<pair<int, int>> adj[MAXN];

pair<int, int> dp_1[32][MAXN], dp_2[32][MAXN];

void count_routes(int n, int m, int p, int r[][2], int q, int g[]){

  for(int i=0; i<n; i++) adj[i].clear();

  for(int i=0; i<m; i++){
    adj[r[i][0]].push_back({i, r[i][1]});
    adj[r[i][1]].push_back({i, r[i][0]});
  }

  for(int i=0; i<n; i++){

    sort(adj[i].begin(), adj[i].end());

    dp_1[0][i] = {adj[i][0].second, adj[i][0].first};
    // vertice, aresta

    if(adj[i].size() > 1){
      dp_2[0][i] = {adj[i][1].second, adj[i][1].first};
    } else dp_2[0][i] = dp_1[0][i];

  }

  for(int k=1; k<32; k++){
    for(int i=0; i<n; i++){

      auto [nxt_1, e_1] = dp_1[k - 1][i];

      if(e_1 == adj[nxt_1][0].first){
        dp_1[k][i] = dp_2[k - 1][nxt_1];
      } else dp_1[k][i] = dp_1[k - 1][nxt_1];

      auto [nxt_2, e_2] = dp_2[k - 1][i];

      if(e_2 == adj[nxt_2][0].first){
        dp_2[k][i] = dp_2[k - 1][nxt_2];
      } else dp_2[k][i] = dp_1[k - 1][nxt_2];

    }
  }

  for(int i=0; i<q; i++){

    int cnt = 0;

    for(int j=0; j<n; j++){

      pair<int, int> cur = {j, -1};

      for(int k=0; k<32; k++){
        if(g[i] & (1LL << k)){
            
          if(cur.second == adj[cur.first][0].first){
            cur = dp_2[k][cur.first];
          } else cur = dp_1[k][cur.first];

        }
      }

      if(cur.first == p) cnt ++;

    }

    answer(cnt);

  }

}

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