제출 #650042

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

garden

/*
u -> second best and others
u + n -> best
*/

#include "garden.h"
#include "gardenlib.h"
#include<bits/stdc++.h>
using namespace std;
#define INF 2000000000
#define MAXN 150000

int N;
vector<pair<int, int> > oriAdj[MAXN + 3]; // {beauty, v}
vector<int> adj[2 * MAXN + 3], revAdj[2 * MAXN + 3];
int dist[2 * MAXN + 3][2], cycleLength[2];
bool visited[2 * MAXN + 3][2];

void addEdgeToNewGraph(int u, int v, int beauty) {
  bool isBestForV = (beauty == oriAdj[v][0].first);
  int resolvedV = (isBestForV ? v + N : v);
  adj[u].push_back(resolvedV);
}

void dfs(int u, int t, int step, int origin) {
  dist[u][t] = step;
  visited[u][t] = true;

  for (auto v: revAdj[u]) {
    if (v == origin) {
      cycleLength[t] = step + 1;
    }

    if (!visited[v][t]) {
      dfs(v, t, step + 1, origin);
    }
  }
}

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

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

  for (int u = 0; u < n; u++) {
    sort(oriAdj[u].begin(), oriAdj[u].end());
  }

  for (int u = 0; u < n; u++) {
    // Add directed edge from u to v or (v + n).
    if (true) {
      auto [beauty, v] = oriAdj[u][0];
      addEdgeToNewGraph(u, v, beauty);
    }

    // Add directed edge from (u + n) to v or (v + n).
    if (true) {
      auto [beauty, v] = oriAdj[u].size() > 1 ? oriAdj[u][1] : oriAdj[u][0];
      addEdgeToNewGraph(u + n, v, beauty);
    }
  }

  // cout <<"\nadj\n";
  // for (int u = 0; u < 2 * n; u++) {
  //   cout << u << ":";
  //   for (auto v: adj[u]) {
  //     cout << " " << v;
  //   }
  //   cout << endl;
  // }

  /*
  Reverse the edges of the new graph.
  This could be done previously, but to make it more understandable, I do it separately.
  */
  for (int u = 0; u < 2 * n; u++) {
    for (auto v: adj[u]) {
      revAdj[v].push_back(u);
    }
  }

  // cout <<"\nrevAdj\n";
  // for (int u = 0; u < 2 * n; u++) {
  //   cout << u << ":";
  //   for (auto v: revAdj[u]) {
  //     cout << " " << v;
  //   }
  //   cout << endl;
  // }

  for (int t = 0; t < 2; t++) {
    cycleLength[t] = -1;
    for (int i = 0; i < 2 * n; i++) {
      dist[i][t] = INF;
      visited[i][t] = false;
    }
  }

  dfs(p, 0, 0, p);
  dfs(p + n, 1, 0, p + n);

  // cout << "\ncycleLength[0]: " << cycleLength[0] << endl;
  // cout << "cycleLength[1]: " << cycleLength[1] << endl;

  // cout << "\ndist0:\n";
  // for (int u = 0; u < 2 * n; u++) {
  //   cout << u << ": " << dist[u][0] << endl;
  // }

  // cout << "\ndist1:\n";
  // for (int u = 0; u < 2 * n; u++) {
  //   cout << u << ": " << dist[u][1] << endl;
  // }

  for (int query = 0; query < q; query++) {
    int ans = 0;
    for (int u = 0; u < n; u++) {
      bool possible = false;
      for (int t = 0; t < 2; t++) {
        if (dist[u][t] == g[query] || (cycleLength[t] != -1 && g[query] >= dist[u][t] && (g[query] - dist[u][t])%cycleLength[t] == 0)) {
          possible = true;
        }

        // if (oriAdj[u].size() == 1) {
        //   if (dist[u + n][t] == g[query] || (cycleLength[t] != -1 && dist[u + n][t] == g[query]%cycleLength[t])) {
        //     possible = true;
        //   }
        // }
      }

      if (possible) {
        ans += 1;
      }
    }

    answer(ans);
  }
}

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