Submission #1104598

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104598		kungarooo	Tropical Garden (IOI11_garden)	C++14	100 / 100	720 ms	36108 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include<bits/stdc++.h>
#define B 150000
using namespace std;
vector<int> v(2*B);
vector<vector<int>> adj(B),T(B*2);
vector<bool> vis(2*B);
int sz=0;
bool findcyclic(int x,int st){
  if(vis[x]&&x==st)return 1;
  else if(vis[x])return 0;
  vis[x]=1;
  sz++;
  bool ret=findcyclic(v[x],st);
  vis[x]=0;
  return ret;
}
vector<int>P1,P2;
void bfs(int x,vector<int>& S){
  queue<pair<int,int>> q;
  vector<bool> vv(B*2);
  q.push({x,0});
  while(!q.empty()){
    int node=q.front().first,we=q.front().second;
    q.pop();
    if(vv[node])continue;
    vv[node]=1;
    if(node<B)S.push_back(we);
    for(auto i:T[node]){
      if(!vv[i])q.push({i,we+1});
    }
  }
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
  for(int i=0;i<M;i++){
    adj[R[i][0]].push_back(R[i][1]);
    adj[R[i][1]].push_back(R[i][0]);
  }
  for(int i=0;i<N;i++){
    if(i==adj[adj[i][0]][0])v[i]=adj[i][0]+B;
    else v[i]=adj[i][0];
    if(adj[i].size()>=2){
      if(adj[adj[i][1]][0]==i)v[B+i]=adj[i][1]+B;
      else v[B+i]=adj[i][1];
    }
    else v[B+i]=v[i];
  }
  int sz1=0,sz2=0;
  if(findcyclic(P,P)){
    sz1=sz;
  }
  sz=0;
  if(findcyclic(P+B,P+B)){
    sz2=sz;
  }
  sz=0;
  for(int i=0;i<N;i++){
    T[v[i]].push_back(i);
    T[v[i+B]].push_back(i+B);
  }
  bfs(P,P1);
  bfs(P+B,P2);
  for(int j=0;j<Q;j++){
    int y0=0;
    for(auto i:P1){
      if(i>G[j])break;
      if(sz1==0){
        if(G[j]==i)y0++;
      }else{
        if((G[j]-i)%sz1==0)y0++;
      }
    }
    for(auto i:P2){
      if(i>G[j])break;
      if(sz2==0){
        if(G[j]==i)y0++;
      }else{
        if((G[j]-i)%sz2==0)y0++;
      }
    }
    answer(y0);
  }
}

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