Submission #1212734

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212734		vincentbucourt1	Tropical Garden (IOI11_garden)	C++20	49 / 100	1 ms	584 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;

const int INF = (int)1e9;

int V, E;
vector<int> deg;
vector<int> adj;
vector<vector<int>> revAdj;
vector<int> distP, distPV;
vector<int> cycleLen;
vector<int> prefModP, prefModPV;

void BFS (vector<int>& dist, int source) {
  dist.assign(2*V, INF);
  dist[source] = 0;
  deque<int> DQ;
  DQ.push_back(source);
  while (!DQ.empty()) {
    int on = DQ.front();
    DQ.pop_front();
    for (int prv : revAdj[on]) {
      if (dist[prv] > dist[on] + 1) {
        dist[prv] = dist[on] + 1;
        DQ.push_back(prv);
      }
    }
  }
}

void makePref (vector<int>& dist, vector<int>& pref, int len) {
  assert((int)dist.size() == 2*V);
  pref.assign(120, 0);
  for (int i = 0; i < V; i++) {
    if (dist[i] != INF) {
      assert(dist[i] < 2*V && dist[i] >= 0);
      pref[dist[i]]++;
    }
  }
  for (int i = 0; i < 120; i++) {
    if (i >= len && len > 0) {
      pref[i] += pref[i - len];
    }
  }
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
  V = N, E = M;
  adj.resize(2*V);
  iota(adj.begin(), adj.end(), 0);
  revAdj.resize(2*V);
  deg.assign(V, 0);
  for (int i = 0; i < E; i++) {
    int a = R[i][0], b = R[i][1];
    if (deg[a] > deg[b]) {
      swap(a, b);
    }
    assert(deg[a] <= deg[b]);
    if (deg[a] == 0 && deg[b] == 0) {
      adj[a] = b+V;
      adj[b] = a+V;
      adj[a+V] = b+V;
      adj[b+V] = a+V;
    }
    else if (deg[a] == 0 && deg[b] >= 1) {
      adj[a] = b;
      adj[a+V] = b;
      if (deg[b] == 1) {
        adj[b+V] = a+V;
      }
    }
    else if (deg[a] == 1) {
      adj[a+V] = b;
      if (deg[b] == 1) {
        adj[b+V] = a;
      }
    }
    deg[a]++, deg[b]++;
  }
  for (int i = 0; i < 2*V; i++) {
    revAdj[adj[i]].push_back(i);
  }

  BFS(distP, P);
  BFS(distPV, P+V);
  // for (int i = 0; i < 2*V; i++) cerr << distPV[i] << " ";
  // cerr << "\n";

  cycleLen.assign(2*V, 0);
  enum State{UNVISITED, VISITING, VISITED};
  vector<State> state(2*V, UNVISITED);
  for (int i = 0; i < 2*V; i++) {
    if (state[i] == UNVISITED) {
      int on = i;
      vector<int> visiting;
      while (state[on] == UNVISITED) {
        // cerr << on << " ";
        visiting.push_back(on);
        state[on] = VISITING;
        on = adj[on];
      }
      // cerr << "|" << on << "|\n";
      if (state[on] == VISITING) {
        int len = 1, j = (int)visiting.size()-1;
        while (visiting[j] != on) {
          j--, len++;
        }
        while (visiting.back() != on) {
          cycleLen[visiting.back()] = len;
          state[visiting.back()] = VISITED;
          visiting.pop_back();
        }
        cycleLen[on] = len;
        assert(visiting.back() == on);
        while (!visiting.empty()) {
          state[visiting.back()] = VISITED;
          visiting.pop_back();
        }
      }
      else {
        assert(state[on] == VISITED);
        for (int val : visiting) {
          state[val] = VISITED;
        }
        visiting.clear();
      }
    }
  }
  // for (int i = 0; i < 2*V; i++) cerr << cycleLen[i] << " ";
  // cerr << "\n";

  makePref(distP, prefModP, cycleLen[P]);
  makePref(distPV, prefModPV, cycleLen[P+V]);

  for (int iq = 0; iq < Q; iq++) {
    int ans = prefModP[G[iq]] + prefModPV[G[iq]];
    answer(ans);
  }
}

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