Submission #1112753

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112753		PagodePaiva	Tropical Garden (IOI11_garden)	C++17	100 / 100	1567 ms	24568 KiB

garden

#include<bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
#define cyc1 cyc
 
using namespace std;
 
const int N = 150010;
vector <array <int, 2>> g[N], gg[N];
int dist[N][2];
int low[N][2];
int nx[N][2];
int back[N][2];
 
void count_routes(int n, int m, int p, int r[][2], int q, int G[]){
    for(int i = 0;i < m;i++){
      gg[r[i][0]].push_back({i, r[i][1]});
      gg[r[i][1]].push_back({i, r[i][0]});
    }
    memset(low, -1, sizeof low);
    memset(nx, -1, sizeof nx);
    for(int i = 0;i < n;i++){
      sort(gg[i].begin(), gg[i].end());
      for(int j = 0;j < min((int)gg[i].size(), 2);j++){
        g[gg[i][j][1]].push_back({gg[i][j][0], i});
        low[i][j] = gg[i][j][0];
        nx[i][j] = gg[i][j][1];
      }
    }
    for(int i = 0;i < N;i++){
      dist[i][0] = dist[i][1] = 1e9+20;
    }
    dist[p][0] = dist[p][1] = 0;
    priority_queue <array <int, 3>> pq;
    pq.push({0, p, 0});
    pq.push({0, p, 1});
    while(!pq.empty()){
      auto [d, v, flag] = pq.top();
      pq.pop();
      d *= -1;
      if(d != dist[v][flag]) continue;
      for(auto [w, x] : g[v]){
        if(w == low[x][0]){
          int fg;
          if(w == low[v][0]) fg = 1;
          else fg = 0;
          if(fg != flag) continue;
          if(dist[v][flag]+1 < dist[x][0]){
            dist[x][0] = dist[v][flag]+1;
            if(v == p){
              if(w == low[v][0]) back[x][0] = 1;
              else back[x][0] = 0;
            }
            else{
              back[x][0] = back[v][flag];
            }
            pq.push({-dist[x][0], x, 0});
            if(low[x][1] == -1){
              if(dist[v][flag]+1 < dist[x][1]){
              dist[x][1] = dist[v][flag]+1;
              if(v == p){
                if(w == low[v][0]) back[x][1] = 1;
                else back[x][1] = 0;
              }
              else{
                back[x][1] = back[v][flag];
              }
              pq.push({-dist[x][1], x, 1});
              }
            }
          }
        }
        else if(w == low[x][1]){
          int fg;
          if(w == low[v][0]) fg = 1;
          else fg = 0;
          if(fg != flag) continue;
          if(dist[v][flag]+1 < dist[x][1]){
            dist[x][1] = dist[v][flag]+1;
            if(v == p){
              if(w == low[v][0]) back[x][1] = 1;
              else back[x][1] = 0;
            }
            else{
              back[x][1] = back[v][flag];
            }
            pq.push({-dist[x][1], x, 1});
          }
        }
      }
    }
    for(int i = 0;i < q;i++){
      int k = G[i];
      int res = 0;
      for(int v = 0;v < n;v++){
        //cout << res << ' ';
        if(dist[v][0] == k) {
          res++;
          continue;
        }
        if(k < dist[v][0]) continue;
        int t = dist[v][0], b = back[v][0];
        if(b == 1){
            if(nx[p][1] == -1){
                b = 0;
            }
        }
        int cyc=0;
        if(b == 0){
          int x = nx[p][0];
          cyc++;
          if(low[p][0] == low[x][0]) cyc += dist[x][1];
          else cyc += dist[x][0];
          int bb = back[x][(low[p][0] == low[x][0] ? 1 : 0)];
          if(bb == 1){
            if(nx[p][1] == -1) bb = 0;
          }
          if(bb == 0){
            if(k % cyc == (dist[v][0]) % cyc){
              res++;
              continue;
            }
            else continue;
          }
          else{
            int cyc2 = 0;
            int xx = nx[p][1];
            cyc2++;
            if(low[p][1] == low[xx][0]) cyc2 += dist[xx][1];
            else cyc2 += dist[xx][0];
            int bbb = back[xx][(low[p][1] == low[xx][0] ? 1 : 0)];
            if(bbb == 1){
              if(k%cyc2 == (dist[v][0] + cyc1)%cyc2){
                res++;
                continue;
              }
            }
            else{
              if(k%(cyc1+cyc2) == (dist[v][0])%(cyc1+cyc2) or k%(cyc1+cyc2) == (dist[v][0]+cyc1)%(cyc1+cyc2)){
                res++;
                continue;
              }
            }
          }
        }
        else{
          int x = nx[p][1];
          cyc++;
          if(low[p][1] == low[x][0]) cyc += dist[x][1];
          else cyc += dist[x][0];
          int bb = back[x][(low[p][1] == low[x][0] ? 1 : 0)];
          if(bb == 1){
            if(k % cyc == (dist[v][0]) % cyc){
              res++;
              continue;
            }
            else continue;
          }
          else{
            int cyc2 = 0;
            int xx = nx[p][0];
            cyc2++;
            if(low[p][0] == low[xx][0]) cyc2 += dist[xx][1];
            else cyc2 += dist[xx][0];
            int bbb = back[xx][(low[p][0] == low[xx][0] ? 1 : 0)];
            if(bbb == 0){
              if(k%cyc2 == (dist[v][0] + cyc1)%cyc2){
                res++;
                continue;
              }
            }
            else{
              if(k%(cyc1+cyc2) == (dist[v][0])%(cyc1+cyc2) or k%(cyc1+cyc2) == (dist[v][0]+cyc1)%(cyc1+cyc2)){
                res++;
                continue;
              }
            }
          }
        }
      }
      answer(res);
    }
}

Compilation message (stderr)

garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:102:13: warning: unused variable 't' [-Wunused-variable]
  102 |         int t = dist[v][0], b = back[v][0];
      |             ^

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