oj.uz

Submission #66485

# Submission time Handle Problem Language Result Execution time Memory
66485 2018-08-10T21:07:03 Z Bodo171 Tropical Garden (IOI11_garden) C++14
0 / 100
 16 ms 14600 KB 
#include "garden.h"
#include "gardenlib.h"
#include <vector>
#include <iostream>
using namespace std;
const int nmax=300005;
int i,nod,old,state,oldstate,nr,x,nxt,cycles,sz1,sz2,j;
vector<int> v[2*nmax];
int p[nmax][2],mare[nmax];
int viz[2*nmax],dist[2][2*nmax],st[2*nmax],cyc[nmax],sz[2*nmax],rel[nmax];
void link_(int A,int B)
{
    if(p[A][0]==-1) p[A][0]=B;
    else if(p[A][1]==-1) p[A][1]=B;
    if(mare[A]==-1) mare[A]=B;
}
void dfs(int B,int x)
{
    for(int i=0;i<v[x].size();i++)
        if(!dist[B][v[x][i]])
    {
        dist[B][v[x][i]]=dist[B][x]+1;
        dfs(B,v[x][i]);
    }
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
  for(i=0;i<N;i++)
    p[i][0]=p[i][1]=mare[i]=-1;
  for(i=0;i<M;i++)
  {
     link_(R[i][0],R[i][1]);
     link_(R[i][1],R[i][0]);
  }
  for(i=0;i<N;i++)
    if(p[i][1]==-1)
       mare[i]=N+1;
  for(nod=0;nod<N;nod++)
    if(!viz[2*nod])
  {
      x=nod;old=-1;state=2*N;nr=0;oldstate=-1;
      while(!viz[x*2+(old==mare[x])])
      {
          state=x*2+(old==mare[x]);
          st[++nr]=state;
          if(oldstate!=-1)v[state].push_back(oldstate);
          if(old==mare[x]&&p[x][1]!=-1) x=p[x][1];
          else x=p[x][0];
          old=state/2;
          viz[state]=1;
          oldstate=state;
      }
      st[nr+1]=x*2+(old==mare[x]);
      if(nr)v[st[nr+1]].push_back(st[nr]);
      if(cyc[st[nr+1]])
         for(i=nr;i>=1;i--)
        {
            x=st[i];nxt=st[i+1];
            cyc[x]=cyc[nxt];
        }
        else
        {
            cycles++;
            for(i=1;i<=nr;i++)
            {
                x=st[i];
                cyc[x]=cycles;
                if(st[i]==st[nr+1])
                {
                    for(int k=i;k<=nr;k++)
                       sz[st[k]]=nr+1-i;
                }
            }

        }
  }
  nr=0;
  for(i=0;i<N;i++)
    if(cyc[2*i]==cyc[2*P]||cyc[2*i]==cyc[2*P+1])
  {
      rel[++nr]=i;
  }
  dist[0][2*P]=dist[1][2*P+1]=1;
  dfs(0,2*P);
  dfs(1,2*P+1);
  for(i=0;i<2;i++)
    for(j=0;j<2*N;j++)
       if(!dist[i][j])
          dist[i][j]=1000*1000*1000+5;
  sz1=sz[2*P];sz2=sz[2*P+1];
  for(i=0; i<Q; i++)
  {
    int ret=0,ok=0;
    G[i]++;
    for(j=1;j<=nr;j++)
    {

        x=2*rel[j];ok=0;
        if(sz1)
        {
          if((dist[0][x]<=G[i]&&(G[i]-dist[0][x])%sz1==0))
             ok=1;
        }
        else
            if(dist[0][x]==G[i])
                ok=1;
        if(viz[2*P+1])
        {
            if(sz2)
        {
          if((dist[1][x]<=G[i]&&(G[i]-dist[1][x])%sz2==0))
             ok=1;
        }
        else
            if(dist[1][x]==G[i])
                ok=1;
        ret+=ok;
        }
    }
    answer(ret);
  }
}

Compilation message

garden.cpp: In function 'void dfs(int, int)':
garden.cpp:19:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v[x].size();i++)
                 ~^~~~~~~~~~~~

Subtask #1
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 14600 KB Output is correct
2 Correct 15 ms 14584 KB Output is correct
3 Correct 15 ms 14560 KB Output is correct
4 Incorrect 16 ms 14548 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 14600 KB Output is correct
2 Correct 15 ms 14584 KB Output is correct
3 Correct 15 ms 14560 KB Output is correct
4 Incorrect 16 ms 14548 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 14600 KB Output is correct
2 Correct 15 ms 14584 KB Output is correct
3 Correct 15 ms 14560 KB Output is correct
4 Incorrect 16 ms 14548 KB Output isn't correct
5 Halted 0 ms 0 KB -