Submission #298992

#	Time	Username	Problem	Language	Result	Execution time	Memory
298992		erd1	Tropical Garden (IOI11_garden)	C++14	69 / 100	5081 ms	9208 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);
}

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;
  for(int i=0; i<Q; i++){
    calc(2*N, G[i]);
    //for(auto i: tmp1)cout << i << " "; cout << endl;
    int ans = 0;
    for(int i = 0; i < N; i++)
      if(tmp1[2*i]/2 == P)ans++;
    answer(ans);
  }
}

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