oj.uz

Submission #1107728

# Submission time Handle Problem Language Result Execution time Memory
1107728 2024-11-02T03:58:55 Z laight Tropical Garden (IOI11_garden) C++17
100 / 100
 1622 ms 65608 KB 
#include "garden.h"
  #include "gardenlib.h"
  #define pb emplace_back
  #include<bits/stdc++.h>
  using namespace std;
  vector<int>g[300005];
  vector<int>g2(600005);
  int jp=0;
  vector<int>g_rev[600005];
  bool cycle=false;
  int c;
  map<int,bool>vs;
  bool vs1[600005],vs2[600005];
  void dfs(int u,int cnt,int pp)
  {
    if(vs[u])
    {
      if(u==pp)
      {
        cycle = true;
        c = cnt;
      }
      return ;
    }
    vs[u]=true;
    dfs(g2[u], cnt+1, pp);
  }
  int cnt_ans1[600005];
  int cnt_ans2[600005];

  void dfs1(int u,int cnt)
  {
    if(vs1[u]) return ;
    vs1[u] = true;
    cnt_ans1[u] = cnt;
    for(auto v:g_rev[u]) dfs1(v,cnt+1);
  }
  void dfs2(int u,int cnt)
  {
    if(vs2[u]) return ;
    vs2[u] = true;
    cnt_ans2[u] = cnt;
    for(auto v:g_rev[u]) dfs2(v,cnt+1);
  }


  void count_routes(int n, int m, int p, int R[][2], int Q, int G[])
  {
    for(int i=0;i<m;i++)
    {
      if(g[R[i][0]].size()<=2) g[R[i][0]].pb(R[i][1]);
      if(g[R[i][1]].size()<=2) g[R[i][1]].pb(R[i][0]);
    }
    for(int i=0;i<n;i++)
    {
      int v = g[i][0];
      if(i==g[v][0]) g2[i] = v+n;
      else  g2[i] = v;
      int vv;
      if(g[i].size()!=1) vv = g[i][1];
      else vv = g[i][0];

      if(i==g[vv][0]) g2[i+n] = vv+n;
      else  g2[i+n] = vv;
    }
    for(int i=0;i<2*n;i++)
    {
      g_rev[g2[i]].pb(i);
    }
    dfs(p,0,p);
    bool cycle1 = cycle;
    int c1 = c;
    cycle=false;
    vs.clear();
    dfs(n+p,0,n+p);
    vs.clear();
    bool cycle2 = cycle;
    int c2 = c;

    dfs1(p,0);
    dfs2(p+n,0);


    for(int k=0;k<Q;k++)
    {
      int d = G[k];
      int ans=0;

      for(int i=0;i<n;i++)
      {
        bool ok = 0;
        int len = d - cnt_ans1[i];
        if(len >= 0 and vs1[i]) {
        if(cycle1 and len%c1 == 0) ok = 1;
        else if(!cycle1 and len == 0) ok = 1;
        }

        len = d - cnt_ans2[i];
        if(len >= 0 and vs2[i]) {
        if(cycle2 and len%c2 == 0) ok = 1;
        else if(!cycle2 and len == 0) ok = 1;
        }

        ans += ok;
      }
      // cout << endl;
      answer(ans);
    }

  }

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29520 KB Output is correct
2 Correct 6 ms 29520 KB Output is correct
3 Correct 5 ms 29520 KB Output is correct
4 Correct 5 ms 29264 KB Output is correct
5 Correct 5 ms 29264 KB Output is correct
6 Correct 5 ms 29520 KB Output is correct
7 Correct 5 ms 29432 KB Output is correct
8 Correct 6 ms 29520 KB Output is correct
9 Correct 6 ms 29520 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29520 KB Output is correct
2 Correct 6 ms 29520 KB Output is correct
3 Correct 5 ms 29520 KB Output is correct
4 Correct 5 ms 29264 KB Output is correct
5 Correct 5 ms 29264 KB Output is correct
6 Correct 5 ms 29520 KB Output is correct
7 Correct 5 ms 29432 KB Output is correct
8 Correct 6 ms 29520 KB Output is correct
9 Correct 6 ms 29520 KB Output is correct
10 Correct 5 ms 29264 KB Output is correct
11 Correct 13 ms 31256 KB Output is correct
12 Correct 20 ms 32000 KB Output is correct
13 Correct 129 ms 61000 KB Output is correct
14 Correct 60 ms 40264 KB Output is correct
15 Correct 66 ms 40520 KB Output is correct
16 Correct 56 ms 39256 KB Output is correct
17 Correct 50 ms 37880 KB Output is correct
18 Correct 22 ms 34636 KB Output is correct
19 Correct 58 ms 40264 KB Output is correct
20 Correct 65 ms 41800 KB Output is correct
21 Correct 54 ms 37704 KB Output is correct
22 Correct 56 ms 37296 KB Output is correct
23 Correct 65 ms 41176 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29520 KB Output is correct
2 Correct 6 ms 29520 KB Output is correct
3 Correct 5 ms 29520 KB Output is correct
4 Correct 5 ms 29264 KB Output is correct
5 Correct 5 ms 29264 KB Output is correct
6 Correct 5 ms 29520 KB Output is correct
7 Correct 5 ms 29432 KB Output is correct
8 Correct 6 ms 29520 KB Output is correct
9 Correct 6 ms 29520 KB Output is correct
10 Correct 5 ms 29264 KB Output is correct
11 Correct 13 ms 31256 KB Output is correct
12 Correct 20 ms 32000 KB Output is correct
13 Correct 129 ms 61000 KB Output is correct
14 Correct 60 ms 40264 KB Output is correct
15 Correct 66 ms 40520 KB Output is correct
16 Correct 56 ms 39256 KB Output is correct
17 Correct 50 ms 37880 KB Output is correct
18 Correct 22 ms 34636 KB Output is correct
19 Correct 58 ms 40264 KB Output is correct
20 Correct 65 ms 41800 KB Output is correct
21 Correct 54 ms 37704 KB Output is correct
22 Correct 56 ms 37296 KB Output is correct
23 Correct 65 ms 41176 KB Output is correct
24 Correct 5 ms 29264 KB Output is correct
25 Correct 103 ms 31056 KB Output is correct
26 Correct 155 ms 33872 KB Output is correct
27 Correct 814 ms 61544 KB Output is correct
28 Correct 900 ms 40264 KB Output is correct
29 Correct 999 ms 40624 KB Output is correct
30 Correct 575 ms 37968 KB Output is correct
31 Correct 432 ms 36884 KB Output is correct
32 Correct 166 ms 32584 KB Output is correct
33 Correct 959 ms 40440 KB Output is correct
34 Correct 959 ms 40520 KB Output is correct
35 Correct 565 ms 37704 KB Output is correct
36 Correct 833 ms 36936 KB Output is correct
37 Correct 756 ms 41288 KB Output is correct
38 Correct 1622 ms 65608 KB Output is correct