Submission #299228

#	Time	Username	Problem	Language	Result	Execution time	Memory
299228		erd1	Tropical Garden (IOI11_garden)	C++14	100 / 100	2826 ms	12920 KiB

garden

#include "garden.h"
#include "gardenlib.h"

#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define pb push_back

vector<int> arr;
vector<int> ans1, ans2, gone;

void dfs(int i, int P, vector<int>& ans){
  if(arr[i] == P)
    return ans[i] = 1, void(0);
  if(!gone[arr[i]])
    gone[arr[i]] = true, dfs(arr[i], P, ans);
  if(ans[arr[i]] != INT_MAX)ans[i] = ans[arr[i]]+1;
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
  arr.resize(2*N, -1);
  for(int i = 0; i < M; i++){
    bool b1 = arr[R[i][0]*2] == -1, b2 = arr[R[i][1]*2] == -1;
    if(b1)arr[R[i][0]*2] = R[i][1]*2 + b2;
    else if(arr[R[i][0]*2+1] == -1)arr[R[i][0]*2+1] = R[i][1]*2 + b2;
    if(b2)arr[R[i][1]*2] = R[i][0]*2 + b1;
    else if(arr[R[i][1]*2+1] == -1)arr[R[i][1]*2+1] = R[i][0]*2 + b1;
  }
  for(int i = 0; i < 2*N; i++)if(arr[i] == -1)arr[i] = arr[i-1];
  ans1.resize(2*N, INT_MAX); ans2.resize(2*N, INT_MAX); gone.resize(2*N, 0);
  for(int i = 0; i < 2*N; i++) if(!gone[i]) dfs(i, 2*P, ans1);
  fill(all(gone), 0);
  for(int i = 0; i < 2*N; i++) if(!gone[i]) dfs(i, 2*P+1, ans2);
  int d1 = 0, d2 = 0; swap(ans1[2*P], d1); swap(ans2[2*P+1], d2);
  for(int j=0; j<Q; j++){
    int ans = 0;
    for(int i = 0; i < N; i++)
      if(ans1[2*i] <= G[j] && (G[j] - ans1[2*i])%d1 == 0 || ans2[2*i] <= G[j] && (G[j] - ans2[2*i])%d2 == 0)
        ans++;
    answer(ans);
  }
}

Compilation message (stderr)

garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:40:28: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   40 |       if(ans1[2*i] <= G[j] && (G[j] - ans1[2*i])%d1 == 0 || ans2[2*i] <= G[j] && (G[j] - ans2[2*i])%d2 == 0)

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