Submission #1260558

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260558		julia_08	Tropical Garden (IOI11_garden)	C++20	0 / 100	3 ms	5700 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[20][MAXN], dp_2[20][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<20; 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++){

      int cur = j;

      for(int k=0; k<30; k++){
        if(g[i] & (1 << k)){
          cur = dp_1[k][cur].first;
        }
      }

      if(cur == p) cnt ++;

    }

    answer(cnt);

  }

}

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