Submission #445027

#	Time	Username	Problem	Language	Result	Execution time	Memory
445027		prvocislo	Tropical Garden (IOI11_garden)	C++17	0 / 100	12 ms	20528 KiB

garden

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

const int maxn = 1.5e5 + 5, inf = 1e9 + 5;
//const int maxn = 15, inf = 1e9 + 5;
struct edge { int v, id; };
bool cmp(const edge &a, const edge &b) { return a.id < b.id; }
struct ans { int a, b; ans(int A = inf-1, int B = inf):a(A), b(B) {} };
vector<edge> g[maxn];
int nx[maxn*2], vis[maxn*2], col[maxn*2];
vector<int> pv[maxn*2], len(maxn*2, inf);
vector<ans> v[maxn*2];
void dfs(int u, const ans &a)
{
  vis[u] = true, v[u].push_back(a);
  for (int i : pv[u])
  {
    if (vis[i]) continue;
    dfs(i, ans(a.a+1, a.b));
  }
}
void count_routes(int n, int m, int p, int e[][2], int q, int qu[])
{
  for (int i = 0; i < m; i++) g[e[i][0]].push_back({e[i][1], i}), g[e[i][1]].push_back({e[i][0], i});
  for (int i = 0; i < n; i++)
  {
    sort(g[i].begin(), g[i].end(), cmp);
    if (g[i].size() < 2) g[i].push_back(g[i][0]);
  }
  for (int l = 0; l < 2; l++) for (int i = 0; i < n; i++)
  {
    nx[l*n+i] = g[i][l].v+(g[i][l].id == g[g[i][l].v][0].id)*n;
    pv[nx[l*n+i]].push_back(l*n+i);
  }
  int c = 0;
  for (int i = 0; i < 2*n; i++)
  {
    if (vis[i]) continue;
    c++;
    int vr = i, cnt = 1;
    while (!col[vr]) vis[vr] = cnt++, col[vr] = c, vr = nx[vr];
    if (col[vr] != c) continue; // tento cyklus sme uz nasli
    int l = cnt - vis[vr];
    len[vr] = l; int v2 = nx[vr];
    while (vr != v2) len[v2] = l, v2 = nx[v2];
  }
  for (int l = 0; l < 2; l++)
  {
    memset(vis, 0, sizeof(vis));
    dfs(l*n+p, ans(0, len[l*n+p]));
  }
  for (int i = 0; i < q; i++)
  {
    int cnt = 0;
    vector<int> kt;
    for (int j = 0; j < n; j++)
    {
      bool ok = false;
      for (const ans &a : v[j]) if ((qu[i] - a.a) % a.b == 0) ok = true;
      cnt += ok;
      if (ok) kt.push_back(j);
    }
    answer(cnt);
  }
}

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