Submission #263473

#	Time	Username	Problem	Language	Result	Execution time	Memory
263473		uacoder123	Tropical Garden (IOI11_garden)	C++14	69 / 100	5061 ms	41080 KiB

garden

        #include <bits/stdc++.h>
        using namespace std;
         #include "garden.h"
 #include "gardenlib.h"
        #define F first
        #define S second
        #define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
        #define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
        #define all(x) (x).begin(), (x).end()
        #define sz(x) lli(x.size())
        #define mp(i,a) make_pair(i,a)
        #define pb(a) push_back(a)
        #define bit(x,b) (x&(1LL<<b))
         
        typedef int lli;
        typedef pair <lli,lli> ii;
        typedef pair <lli,ii> iii;
        typedef vector <lli> vi;

// #define MAX_M  1000000
// #define MAX_Q  2000

// static int N, M, P, Q;
// static int R[MAX_M][2];
// static int G[MAX_Q];
// static int solutions[MAX_Q];
// static int answers[MAX_Q];
// static int answer_count;

// inline 
// void my_assert(int e) {if (!e) abort();}
// void read_input()
// {
//   int i;
//   my_assert(3==scanf("%d %d %d",&N,&M,&P));
//   for(i=0; i<M; i++)
//     my_assert(2==scanf("%d %d",&R[i][0],&R[i][1]));
//   my_assert(1==scanf("%d",&Q));
//   for(i=0; i<Q; i++)
//     my_assert(1==scanf("%d",&G[i]));
//   for(i=0; i<Q; i++)
//     my_assert(1==scanf("%d",&solutions[i]));
// }

// void answer(int x)
// {
//   if(answer_count>=Q) {
//     printf("Incorrect.  Too many answers.\n");
//     exit(0);
//   }
//   answers[answer_count] = x;
//   answer_count++;
// }
        lli n,m,d,g;
        lli ed[300001][2],lim=2000000000,cur,ch=0,co=0,arr[2001],nex[300001],vis[300001],v2[300001];
        vi al[300001];
        vector<iii> pos[300001],v,v1;
        lli lev[300001],ya=0;
        bool cmp(lli a,lli b)
        {
          return (a%m)<(b%m);
        }
        void dfs1(lli node,int l)
        {
          lev[node]=l;
          vis[node]=1;
          if(!vis[nex[node]])
            dfs1(nex[node],l+1);
          else
          {
            if(v2[nex[node]]==-2)
            {
              cur=nex[node];
              co=0;
              while(1)
              {
                v2[cur]=3;
                if(ed[cur][0]==d)
                {
                  v1.pb(mp(cur,mp(0,0)));
                }
                co++;
                if(cur==node)
                  break;
                cur=nex[cur];
              }
              for(int i=0;i<v1.size();++i)
                v.pb(mp(v1[i].F,mp(v1[i].S.F,co)));
            }
            else
            {
              v2[node]=max(1,v2[node]);
              ya=lev[nex[node]]-1;
              for(int i=0;i<pos[nex[node]].size();++i)
                v.pb(pos[nex[node]][i]);
            }
          }
          if(ya!=-lim)
          {
            lev[node]=ya;
            ya--;
          }
          v2[node]=max(1,v2[node]);
          if(v2[node]!=3&&ed[node][0]==d)
            v.pb(mp(node,mp((((ed[node][0]==d)?0:1)),lim)));
          for(int i=0;i<v.size();++i)
            pos[node].pb(v[i]);
        }
        void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
        {
          n=N;
          m=M;
          d=P;
          for(lli i=0;i<m;++i)
          {
            ed[i][0]=R[i][0];
            ed[i][1]=R[i][1];
            ed[i+m][0]=R[i][1];
            ed[i+m][1]=R[i][0];
            al[R[i][0]].pb(i);
            al[R[i][1]].pb(i+m);
          }
          for(lli i=0;i<n;++i)
            sort(all(al[i]),cmp);
          g=Q;
          for(lli i=0;i<g;++i)
            arr[i]=G[i];
          for(lli i=0;i<2*m;++i)
          {
            v2[i]=-2;
            if(al[ed[i][1]].size()==1)
              nex[i]=al[ed[i][1]][0];
            else if((al[ed[i][1]][0]%m)!=(i%m))
              nex[i]=al[ed[i][1]][0];
            else
              nex[i]=al[ed[i][1]][1];
          }
          memset(vis,0,sizeof(vis));
          for(lli i=0;i<n;++i)
            if(!vis[al[i][0]])
            {
              v.clear();
              v1.clear();
              ya=-lim;
              dfs1(al[i][0],0);
            }
          for(lli i=0;i<g;++i)
          {
            co=0;
            for(lli j=0;j<n;++j)
            {
              for(int k=0;k<pos[al[j][0]].size();++k)
              {
                if(pos[al[j][0]].size()>8)
                  exit(1);
                if(v2[al[j][0]]!=3||lev[al[j][0]]<=lev[pos[al[j][0]][k].F])
                {
                  if(arr[i]>=(lev[pos[al[j][0]][k].F]-lev[al[j][0]]+pos[al[j][0]][k].S.F)&&(arr[i]-(lev[pos[al[j][0]][k].F]-lev[al[j][0]]+pos[al[j][0]][k].S.F))%pos[al[j][0]][k].S.S==0)
                  {
                    co++;
                    break;
                  }
                }
                else
                {
                  if(arr[i]>=(pos[al[j][0]][k].S.F+pos[al[j][0]][k].S.S-(lev[al[j][0]]-lev[pos[al[j][0]][k].F]))&&(arr[i]-(pos[al[j][0]][k].S.F+pos[al[j][0]][k].S.S-(lev[al[j][0]]-lev[pos[al[j][0]][k].F])))%pos[al[j][0]][k].S.S==0)
                  {
                    co++;
                    break;
                  }  
                }
              }
            }
            answer(co);
          }
        }

// int main()
// {
//   int correct, i;

//   read_input();
//   answer_count = 0;
//   count_routes(N,M,P,R,Q,G);

//   if(answer_count!=Q) {
//     printf("Incorrect.  Too few answers.\n");
//     exit(0);
//   }

//   correct = 1;
//   for(i=0; i<Q; i++)
//     if(answers[i]!=solutions[i])
//       correct = 0;
//   if(correct)
//     printf("Correct.\n");
//   else {
//     printf("Incorrect.\n");
//     printf("Expected: ");
//     for(i=0; i<Q; i++)
//       printf("%d ",solutions[i]);
//     printf("\nReturned: ");
//     for(i=0; i<Q; i++)
//       printf("%d ",answers[i]);
//   }
//   return 0;
// }

Compilation message (stderr)

garden.cpp: In function 'void dfs1(lli, int)':
garden.cpp:87:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |               for(int i=0;i<v1.size();++i)
      |                           ~^~~~~~~~~~
garden.cpp:94:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |               for(int i=0;i<pos[nex[node]].size();++i)
      |                           ~^~~~~~~~~~~~~~~~~~~~~~
garden.cpp:106:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |           for(int i=0;i<v.size();++i)
      |                       ~^~~~~~~~~
garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:152:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |               for(int k=0;k<pos[al[j][0]].size();++k)
      |                           ~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 49 / 49
• Subtask 2: 20 / 20
• Subtask 3: 0 / 31