Submission #1202690

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202690		aykhn	Tropical Garden (IOI11_garden)	C++20	49 / 100	39 ms	41032 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>

using namespace std;

const int MXN = 3e5 + 5;

vector<int> adj[MXN];
vector<array<int, 2>> g[MXN];
int incyc[MXN], par[MXN];
int used[MXN];
int sz[2] = {0, 0};

void dfs(int a, int f)
{
  used[a] = 1;
  for (int &v : adj[a])
  {
    if (used[v] == 2) continue;
    if (used[v] == 0)
    {
      par[v] = a;
      dfs(v, f);
    }
    else
    {
      int e = a;
      while (1)
      {
        sz[f]++;
        incyc[e] = 1;
        if (e == v) break;
        e = par[e];
      }
    }
  }
  used[a] = 2;
}

void add_edge(int u, int v)
{
  adj[v].push_back(u);
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
  for (int i = 0; i < M; i++)
  {
    auto [u, v] = R[i];
    g[u].push_back({i, v});
    g[v].push_back({i, u});
  } 
  for (int i = 0; i < N; i++)
  {
    if (g[i].empty()) continue;
    sort(g[i].begin(), g[i].end());
    int A = g[i][0][1];
    if (g[A][0][1] == i) A = A * 2 + 1;
    else A = A * 2;
    add_edge(2 * i, A);
    if (g[i].size() == 1) 
    {
      add_edge(2 * i + 1, A);
      continue;
    }
    A = g[i][1][1];
    if (g[A][0][1] == i) A = A * 2 + 1;
    else A = A * 2;
    add_edge(2 * i + 1, A);
  }
  dfs(P * 2, 0);
  dfs(P * 2 + 1, 1);
  int d[2][N * 2], seen[2][N * 2];
  for (int i = 0; i < 2; i++)
  {
    fill(d[i], d[i] + N * 2, -1);
    fill(seen[i], seen[i] + N * 2, 0);
    queue<int> q;
    d[i][P * 2 + i] = 0, q.push(P * 2 + i);
    while (!q.empty())
    {
      int a = q.front();
      seen[i][a] |= incyc[a];
      q.pop();
      for (int &v : adj[a])
      {
        if (d[i][v] != -1) continue;
        d[i][v] = d[i][a] + 1;
        seen[i][v] = seen[i][a];
        q.push(v);
      }
    }
  }
  for (int i = 0; i < Q; i++)
  {
    int x = G[i], res = 0;
    for (int j = 0; j < N; j++)
    {
      int ok = 0;
      for (int l = 0; l < 2; l++)
      {
        if (d[l][2 * j] == -1 || d[l][2 * j] > x) continue;
        if (seen[l][2 * j]) ok |= (x - d[l][2 * j]) % sz[l] == 0;
        else ok |= d[l][2 * j] == x;
      }
      res += ok;
    }
    answer(res);
  }
}

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