Submission #299027

#	Time	Username	Problem	Language	Result	Execution time	Memory
299027		erd1	Tropical Garden (IOI11_garden)	C++14	100 / 100	2873 ms	14136 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
typedef int64_t lld;
typedef pair<int, int> pii;

vector<pii> to;
vector<int> arr, arr2, tmp1, tmp2;

void calc(int n, int b){
  tmp2.resize(n); tmp1.resize(n);
  iota(all(tmp1), 0); arr2 = arr;
  do{
    //for(auto i: tmp1)cout << i << " "; cout << endl;
    //for(auto i: arr2)cout << i << " "; cout << endl;
    if(b&1)
      for(int i = 0; i < n; i++)tmp1[i] = arr2[tmp1[i]];
    for(int i = 0; i < n; i++)tmp2[i] = arr2[arr2[i]];
    arr2 = tmp2;
  }while(b>>=1);
}

vector<int> ans1, ans2, gone;

void dfs(int i, int P, vector<int>& ans){
  if(arr[i] == P){
    ans[i] = 1;
    return;
  }
  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[]) {
  to.resize(N, {-1, -1}); arr.resize(2*N);
  for(int i = 0; i < M; i++){
    if(to[R[i][0]].ff == -1)to[R[i][0]].ff = R[i][1];
    else if(to[R[i][0]].ss == -1)to[R[i][0]].ss = R[i][1];
    if(to[R[i][1]].ff == -1)to[R[i][1]].ff = R[i][0];
    else if(to[R[i][1]].ss == -1)to[R[i][1]].ss = R[i][0];
  }
  for(int i = 0; i < N; i++){
    if(to[i].ss == -1)to[i].ss = to[i].ff;
    arr[2*i] = 2*to[i].ff + (to[to[i].ff].ff == i);
    arr[2*i+1] = 2*to[i].ss + (to[to[i].ss].ff == i);
  }
  //for(auto i: to)cout << i.ff << " " << i.ss << "  "; cout << endl;
  //for(auto i: arr)cout << i << " "; cout << endl;
  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);
  //for(auto i: ans1)cout << i << " "; cout << endl;
  //for(auto i: ans2)cout << i << " "; cout << endl;
  int d1 = 0, d2 = 0; swap(ans1[2*P], d1); swap(ans2[2*P+1], d2);
  for(int j=0; j<Q; j++){
    //for(auto i: tmp1)cout << i << " "; cout << endl;
    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:69:28: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   69 |       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++;

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