Submission #986883

#	Time	Username	Problem	Language	Result	Execution time	Memory
986883		huutuan	Tropical Garden (IOI11_garden)	C++14	0 / 100	8 ms	27480 KiB

garden

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

#include <bits/stdc++.h>

using namespace std;

const int N=3e5+10;
int n, m, p;
vector<int> g[N], gg[N];
int nxt[N], vis[N], on_cycle[N], dep[N], cnt[N];
vector<int> vv[N];
int ans[N];

void dfs(int u){
   for (int v:gg[u]) if (dep[v]==-1){
      dep[v]=dep[u]+1;
      dfs(v);
   }
}

void count_routes(int _N, int M, int P, int R[][2], int Q, int G[])
{
   n=_N, m=M, p=P;
   for (int i=0; i<m; ++i){
      int u=R[i][0], v=R[i][1];
      g[u].push_back(v);
      g[v].push_back(u);
   }
   for (int u=0; u<n; ++u) if (g[u].size()){
      int v=g[u][0];
      nxt[u<<1]=v<<1|(g[v][0]==u);
      gg[nxt[u<<1]].push_back(u<<1);
      int v2=g[u][0];
      if ((int)g[u].size()>=2) v2=g[u][1];
      nxt[u<<1|1]=v2<<1|(g[v2][0]==u);
      gg[nxt[u<<1|1]].push_back(u<<1|1);
   }
   vector<int> cycle;
   {
      int u=p<<1;
      while (1){
         cycle.push_back(u); vis[u]=1;
         u=nxt[u];
         if (vis[u]) break;
      }
      cycle.erase(cycle.begin(), find(cycle.begin(), cycle.end(), u));
      for (int i:cycle) on_cycle[i]=1;
   }
   memset(dep, -1, sizeof dep);
   p<<=1;
   dep[p]=0;
   dfs(p);
   if (!on_cycle[p]){
      for (int i=0; i<(n<<1); i+=2) if (dep[i]!=-1) ++cnt[dep[i]];
      for (int i=0; i<Q; ++i) ans[i]+=(G[i]<N?cnt[G[i]]:0);
   }else{
      int mod=cycle.size();
      for (int i=0; i<(n<<1); i+=2) if (dep[i]!=-1) vv[dep[i]%mod].push_back(dep[i]);
      for (int i=0; i<mod; ++i) sort(vv[i].begin(), vv[i].end());
      for (int i=0; i<Q; ++i) ans[i]+=(upper_bound(vv[G[i]%mod].begin(), vv[G[i]%mod].end(), G[i])-vv[G[i]%mod].begin());
   }
   memset(dep, -1, sizeof dep);
   memset(cnt, 0, sizeof cnt);
   for (int i=0; i<N; ++i) vv[i].clear();
   p|=1;
   dep[p]=0;
   dfs(p);
   if (!on_cycle[p]){
      for (int i=0; i<(n<<1); i+=2) if (dep[i]!=-1) ++cnt[dep[i]];
      for (int i=0; i<Q; ++i) ans[i]+=(G[i]<N?cnt[G[i]]:0);
   }else{
      int mod=cycle.size();
      for (int i=0; i<(n<<1); i+=2) if (dep[i]!=-1) vv[dep[i]%mod].push_back(dep[i]);
      for (int i=0; i<mod; ++i) sort(vv[i].begin(), vv[i].end());
      for (int i=0; i<Q; ++i) ans[i]+=(upper_bound(vv[G[i]%mod].begin(), vv[G[i]%mod].end(), G[i])-vv[G[i]%mod].begin());
   }
   for (int i=0; i<Q; ++i) answer(ans[i]);
}

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