제출 #347847

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
347847		milleniumEeee	열대 식물원 (Tropical Garden) (IOI11_garden)	C++17	0 / 100	4 ms	4332 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
#define pii pair<int, int>
#define fr first
#define sc second
#define pb push_back
#define mk make_pair
#define szof(s) (int)s.size()
using namespace std;
 
const int MAXN = 150005;
 
int n, m, p;
vector <pii> edges;
vector <pii> g[MAXN]; //id, vertex
int mn[MAXN], mx[MAXN];
pii table[2][MAXN][30];

int get(int v, int len) {
  int ind = -1;
  int cur = v;
  for (int i = 30; i >= 0; i--) {
    if (len & (1 << i)) {
      if (cur == v) {
        cur = table[0][cur][i].second;
        ind = table[0][cur][i].first;
      } else {
        if (ind != g[cur][0].first) {
          cur = table[0][cur][i].second;
          ind = table[0][cur][i].first;
        } else {
          cur = table[1][cur][i].second;
          ind = table[1][cur][i].first;
        }
      }
    }
  }
  return cur;
}

int solve(int k) {
  int ans = 0;
  for (int v = 0; v < n; v++) {
    if (get(v, k) == p) {
      ans++;
    }
  }
  return ans;
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
  n = N;
  m = M;
  p = P;
  for (int i = 0; i < M; i++) {
    int x = R[i][0];
    int y = R[i][1];
    edges.pb({x, y});
    if (szof(g[x]) < 2) {
      g[x].push_back({i, y});
    }
    if (szof(g[y]) < 2) {
      g[y].push_back({i, x});
    }
  }
  for (int i = 0; i < n; i++) {
    if (szof(g[i]) < 2) {
      g[i].pb(g[i][0]);
    }
  }
  /*
  g[vertex][0] = min1
  g[vertex][1] = min2
  */
  for (int v = 0; v < n; v++) {
    table[0][v][0] = g[v][0];
    table[1][v][0] = g[v][1];
  }
  for (int pw = 1; pw < 30; pw++) {
    for (int v = 0; v < n; v++) {
      for (int tp = 0; tp <= 1; tp++) {
        int to = table[tp][v][pw - 1].second;
        int ind = table[tp][v][pw - 1].first;
        if (ind != g[to][0].first) {
          table[tp][v][pw] = table[0][to][pw - 1];
        } else {
          table[tp][v][pw] = table[1][to][pw - 1];
        }        
      }
    }
  }
  for (int i = 0; i < Q; i++) {
    answer(solve(G[i]));
  }
  return;
}

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