oj.uz

답안 #1104853

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1104853 2024-10-24T14:25:55 Z sweed 열대 식물원 (Tropical Garden) (IOI11_garden) C++14
0 / 100
 9 ms 41552 KB 
 #include "garden.h"
  #include "gardenlib.h"
  #define pb emplace_back
  #include<bits/stdc++.h>
  using namespace std;
  int up[600005][100];
  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;
  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(vs[u]) return ;
    vs[u] = true;
    cnt_ans1[u] = cnt;
    for(auto v:g_rev[u]) dfs1(v,cnt+1);
  }
  void dfs2(int u,int cnt)
  {
    if(vs[u]) return ;
    vs[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);
    vs.clear();
    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 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
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 41552 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 41552 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 41552 KB Output isn't correct
2 Halted 0 ms 0 KB -