Submission #1208918

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208918		HappyCapybara	Tropical Garden (IOI11_garden)	C++20	100 / 100	1383 ms	22800 KiB

garden

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

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
  vector<vector<int>> mb(2, vector<int>(N, -1));
  for (int i=0; i<M; i++){
    if (mb[0][R[i][0]] == -1) mb[0][R[i][0]] = i;
    else if (mb[1][R[i][0]] == -1) mb[1][R[i][0]] = i;
    if (mb[0][R[i][1]] == -1) mb[0][R[i][1]] = i;
    else if (mb[1][R[i][1]] == -1) mb[1][R[i][1]] = i;
  }
  for (int i=0; i<N; i++){
    if (mb[1][i] == -1) mb[1][i] = mb[0][i];
  }
  vector<int> g(N*2);
  for (int i=0; i<N; i++){
    int e1 = mb[0][i], e2 = mb[1][i];
    int n1 = R[e1][0]+R[e1][1]-i, n2 = R[e2][0]+R[e2][1]-i;
    g[2*i] = 2*n1+(e1 == mb[0][n1]);
    g[2*i+1] = 2*n2+(e2 == mb[0][n2]);
  }
  vector<vector<int>> rg(N*2);
  for (int i=0; i<2*N; i++) rg[g[i]].push_back(i);
  int p1c = -1, p2c = -1;
  vector<int> p1d(2*N, -1), p2d(2*N, -1);
  queue<pair<int,int>> q;
  q.push({2*P, 0});
  while (!q.empty()){
    int cur = q.front().first, dist = q.front().second;
    q.pop();
    if (p1d[cur] != -1) continue;
    p1d[cur] = dist;
    for (int next : rg[cur]) q.push({next, dist+1});
  }
  q.push({2*P+1, 0});
  while (!q.empty()){
    int cur = q.front().first, dist = q.front().second;
    q.pop();
    if (p2d[cur] != -1) continue;
    p2d[cur] = dist;
    for (int next : rg[cur]) q.push({next, dist+1});
  }
  vector<bool> seen(2*N, false);
  int cur = 2*P, dist = 0;
  while (!seen[cur]){
    seen[cur] = true;
    cur = g[cur];
    dist++;
  }
  if (cur == 2*P) p1c = dist;
  seen.assign(2*N, false);
  cur = 2*P+1; dist = 0;
  while (!seen[cur]){
    seen[cur] = true;
    cur = g[cur];
    dist++;
  }
  if (cur == 2*P+1) p2c = dist;
  /*for (int i=0; i<N; i++) cout << mb[0][i] << " ";
  cout << endl;
  for (int i=0; i<N; i++) cout << mb[1][i] << " ";
  cout << endl;
  for (int i=0; i<2*N; i++) cout << g[i] << " ";
  cout << endl;
  for (int i=0; i<2*N; i++) cout << p1d[i] << " ";
  cout << endl;
  for (int i=0; i<2*N; i++) cout << p2d[i] << " ";
  cout << endl;*/
  for (int i=0; i<Q; i++){
    int res = 0;
    for (int j=0; j<N; j++){
      if (p1d[2*j] != -1 && (p1d[2*j] == G[i] || (G[i] > p1d[2*j] && p1c != -1 && (G[i]-p1d[2*j]) % p1c == 0))) res++;
      else if (p2d[2*j] != -1 && (p2d[2*j] == G[i] || (G[i] > p2d[2*j] && p2c != -1 && (G[i]-p2d[2*j]) % p2c == 0))) res++;
    }
    answer(res);
  }
}

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