oj.uz

Submission #1104858

# Submission time Handle Problem Language Result Execution time Memory
1104858 2024-10-24T14:35:18 Z sweed Tropical Garden (IOI11_garden) C++14
69 / 100
 5000 ms 84224 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,vs1,vs2;
  void dfs(int u,int cnt,int pp)
  {
    if(vs[u]) 
    {
      if(u==pp)
      {
        cycle = true;
        c = cnt;
      }
      return ;
    }
    vs[u]=true;
    for(auto v:g2[u])
    {
      dfs(v,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].pb(v+n);
      else  g2[i].pb(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].pb(vv+n);
      else  g2[i+n].pb(vv);
    }
    for(int i=0;i<2*n;i++)
    {
      g_rev[g2[i][0]].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;
        continue ;

        // bool ch=true;
        // if(cycle1 and (d-cnt_ans1[i])%c1==0) 
        // {
        //     ans++;
        //     ch=false;
        // } 
        // else if(!cycle1 and d==cnt_ans1[i])
        // {
        //   ans++;
        //   ch=false;
        // }
        // if(!ch) continue;
        // if(cycle2 and (d-cnt_ans2[i])%c2==0) 
        // {
        //     ans++;
        //     ch=false;
        // } 
        // else if(!cycle2 and d==cnt_ans2[i])
        // {
        //   ans++;
        //   ch=false;
        // }
        // cout << ans << ' ' << i << endl;
      }
      // cout << endl;
      answer(ans);
    }
    
  }

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 39760 KB Output is correct
2 Correct 8 ms 39504 KB Output is correct
3 Correct 8 ms 39928 KB Output is correct
4 Correct 6 ms 39248 KB Output is correct
5 Correct 8 ms 39248 KB Output is correct
6 Correct 9 ms 39928 KB Output is correct
7 Correct 7 ms 39248 KB Output is correct
8 Correct 8 ms 39504 KB Output is correct
9 Correct 9 ms 39504 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 39760 KB Output is correct
2 Correct 8 ms 39504 KB Output is correct
3 Correct 8 ms 39928 KB Output is correct
4 Correct 6 ms 39248 KB Output is correct
5 Correct 8 ms 39248 KB Output is correct
6 Correct 9 ms 39928 KB Output is correct
7 Correct 7 ms 39248 KB Output is correct
8 Correct 8 ms 39504 KB Output is correct
9 Correct 9 ms 39504 KB Output is correct
10 Correct 8 ms 39248 KB Output is correct
11 Correct 25 ms 44728 KB Output is correct
12 Correct 42 ms 47688 KB Output is correct
13 Correct 242 ms 84224 KB Output is correct
14 Correct 155 ms 72520 KB Output is correct
15 Correct 273 ms 78152 KB Output is correct
16 Correct 187 ms 66376 KB Output is correct
17 Correct 144 ms 62624 KB Output is correct
18 Correct 41 ms 49736 KB Output is correct
19 Correct 143 ms 72388 KB Output is correct
20 Correct 239 ms 78216 KB Output is correct
21 Correct 175 ms 66376 KB Output is correct
22 Correct 133 ms 62280 KB Output is correct
23 Correct 129 ms 75388 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 39760 KB Output is correct
2 Correct 8 ms 39504 KB Output is correct
3 Correct 8 ms 39928 KB Output is correct
4 Correct 6 ms 39248 KB Output is correct
5 Correct 8 ms 39248 KB Output is correct
6 Correct 9 ms 39928 KB Output is correct
7 Correct 7 ms 39248 KB Output is correct
8 Correct 8 ms 39504 KB Output is correct
9 Correct 9 ms 39504 KB Output is correct
10 Correct 8 ms 39248 KB Output is correct
11 Correct 25 ms 44728 KB Output is correct
12 Correct 42 ms 47688 KB Output is correct
13 Correct 242 ms 84224 KB Output is correct
14 Correct 155 ms 72520 KB Output is correct
15 Correct 273 ms 78152 KB Output is correct
16 Correct 187 ms 66376 KB Output is correct
17 Correct 144 ms 62624 KB Output is correct
18 Correct 41 ms 49736 KB Output is correct
19 Correct 143 ms 72388 KB Output is correct
20 Correct 239 ms 78216 KB Output is correct
21 Correct 175 ms 66376 KB Output is correct
22 Correct 133 ms 62280 KB Output is correct
23 Correct 129 ms 75388 KB Output is correct
24 Correct 11 ms 39248 KB Output is correct
25 Correct 4038 ms 44800 KB Output is correct
26 Execution timed out 5040 ms 49736 KB Time limit exceeded
27 Halted 0 ms 0 KB -