Submission #445061

#	Time	Username	Problem	Language	Result	Execution time	Memory
445061		prvocislo	Tropical Garden (IOI11_garden)	C++17	0 / 100	9 ms	14540 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], d[2][maxn*2], len[2];
vector<int> pv[maxn*2];
void dfs(int u, int i)
{
  vis[u] = true;
  for (int v : pv[u])
  {
    if (vis[v])
    {
      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++) 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);
  }
  for (int l = 0; l < 2; l++)
  {
    memset(vis, 0, sizeof(vis));
    memset(d[l], -1, sizeof(d[l]));
    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] >= 0 && ((!len[l] && d[l][j] == qu[i]) || (len[l] && (qu[i] - d[l][j]) % len[l] == 0))) ok = true; 
      cnt += ok;
    }
    answer(cnt);
  }
}

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