Submission #445078

#	Time	Username	Problem	Language	Result	Execution time	Memory
445078		prvocislo	Tropical Garden (IOI11_garden)	C++17	100 / 100	2739 ms	34644 KiB

garden

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

const int maxn = 1.5e5 + 5, inf = 2e9 + 5;
struct ans { int a, b; ans(int A = inf-1, int B = inf):a(A), b(B) {} };
int d[2][maxn*2], len[2], cnt[maxn * 2];
vector<int> g[maxn*2];
void dfs(int u, int i)
{
  for (int v : g[u])
  {
    if (d[i][v] != inf)
    {
      if (d[i][v] == 0) len[i] = d[i][u] + 1;
      continue;
    }
    d[i][v] = d[i][u] + 1;
    dfs(v, i);
  }
}
void count_routes(int n, int m, int p, int e[][2], int q, int qu[])
{
  for (int i = 0; i < m; i++)
  {
    for (int j = 0; j < 2; j++)
    {
      int u = e[i][j], v = e[i][j^1];
      if (cnt[u] < 2) g[v + (cnt[v] == 0) * n].push_back(u + cnt[u] * n);
    }
    for (int j = 0; j < 2; j++) cnt[e[i][j]]++;
  }
  for (int i = 0; i < n; i++)
  {
    if (cnt[i] >= 2) continue;
    for (int j : g[i+n]) g[i].push_back(j);
    g[i+n].clear();
  }
  for (int l = 0; l < 2; l++)
  {
    fill(d[l], d[l] + maxn * 2, inf); len[l] = inf;
    d[l][l*n+p] = 0;
    dfs(l*n+p, l);
  }
  for (int i = 0; i < q; i++)
  {
    int cnt = 0;
    for (int j = 0; j < n; j++)
    {
      bool ok = false;
      for (int l = 0; l < 2; l++) 
        if (d[l][j] <= qu[i] && (qu[i] - d[l][j]) % len[l] == 0) ok = true; 
      cnt += ok;
    }
    answer(cnt);
  }
}

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