oj.uz

Submission #986893

# Submission time Handle Problem Language Result Execution time Memory
986893 2024-05-21T14:00:42 Z huutuan Tropical Garden (IOI11_garden) C++14
0 / 100
 10 ms 28252 KB 
#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;
   memset(vis, 0, sizeof vis);
   memset(on_cycle, 0, sizeof on_cycle);
   cycle.clear();
   {
      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;
   }
   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.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 28252 KB Output is correct
2 Correct 10 ms 28048 KB Output is correct
3 Correct 10 ms 28252 KB Output is correct
4 Correct 10 ms 28088 KB Output is correct
5 Correct 10 ms 27996 KB Output is correct
6 Incorrect 10 ms 28252 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 28252 KB Output is correct
2 Correct 10 ms 28048 KB Output is correct
3 Correct 10 ms 28252 KB Output is correct
4 Correct 10 ms 28088 KB Output is correct
5 Correct 10 ms 27996 KB Output is correct
6 Incorrect 10 ms 28252 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 28252 KB Output is correct
2 Correct 10 ms 28048 KB Output is correct
3 Correct 10 ms 28252 KB Output is correct
4 Correct 10 ms 28088 KB Output is correct
5 Correct 10 ms 27996 KB Output is correct
6 Incorrect 10 ms 28252 KB Output isn't correct
7 Halted 0 ms 0 KB -