oj.uz

Submission #263473

# Submission time Handle Problem Language Result Execution time Memory
263473 2020-08-13T17:32:12 Z uacoder123 Tropical Garden (IOI11_garden) C++14
69 / 100
 5000 ms 41080 KB 
        #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

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.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 15744 KB Output is correct
2 Correct 11 ms 15744 KB Output is correct
3 Correct 13 ms 15744 KB Output is correct
4 Correct 11 ms 15616 KB Output is correct
5 Correct 10 ms 15616 KB Output is correct
6 Correct 12 ms 15744 KB Output is correct
7 Correct 11 ms 15616 KB Output is correct
8 Correct 11 ms 15744 KB Output is correct
9 Correct 16 ms 16128 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 15744 KB Output is correct
2 Correct 11 ms 15744 KB Output is correct
3 Correct 13 ms 15744 KB Output is correct
4 Correct 11 ms 15616 KB Output is correct
5 Correct 10 ms 15616 KB Output is correct
6 Correct 12 ms 15744 KB Output is correct
7 Correct 11 ms 15616 KB Output is correct
8 Correct 11 ms 15744 KB Output is correct
9 Correct 16 ms 16128 KB Output is correct
10 Correct 11 ms 15616 KB Output is correct
11 Correct 22 ms 17792 KB Output is correct
12 Correct 39 ms 19576 KB Output is correct
13 Correct 89 ms 40952 KB Output is correct
14 Correct 114 ms 26876 KB Output is correct
15 Correct 140 ms 30712 KB Output is correct
16 Correct 114 ms 27640 KB Output is correct
17 Correct 112 ms 26460 KB Output is correct
18 Correct 38 ms 19328 KB Output is correct
19 Correct 110 ms 26748 KB Output is correct
20 Correct 138 ms 30840 KB Output is correct
21 Correct 120 ms 28152 KB Output is correct
22 Correct 130 ms 27512 KB Output is correct
23 Correct 113 ms 27768 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 15744 KB Output is correct
2 Correct 11 ms 15744 KB Output is correct
3 Correct 13 ms 15744 KB Output is correct
4 Correct 11 ms 15616 KB Output is correct
5 Correct 10 ms 15616 KB Output is correct
6 Correct 12 ms 15744 KB Output is correct
7 Correct 11 ms 15616 KB Output is correct
8 Correct 11 ms 15744 KB Output is correct
9 Correct 16 ms 16128 KB Output is correct
10 Correct 11 ms 15616 KB Output is correct
11 Correct 22 ms 17792 KB Output is correct
12 Correct 39 ms 19576 KB Output is correct
13 Correct 89 ms 40952 KB Output is correct
14 Correct 114 ms 26876 KB Output is correct
15 Correct 140 ms 30712 KB Output is correct
16 Correct 114 ms 27640 KB Output is correct
17 Correct 112 ms 26460 KB Output is correct
18 Correct 38 ms 19328 KB Output is correct
19 Correct 110 ms 26748 KB Output is correct
20 Correct 138 ms 30840 KB Output is correct
21 Correct 120 ms 28152 KB Output is correct
22 Correct 130 ms 27512 KB Output is correct
23 Correct 113 ms 27768 KB Output is correct
24 Correct 12 ms 15744 KB Output is correct
25 Correct 212 ms 17916 KB Output is correct
26 Correct 347 ms 19584 KB Output is correct
27 Correct 2606 ms 41080 KB Output is correct
28 Correct 4148 ms 28664 KB Output is correct
29 Execution timed out 5061 ms 32516 KB Time limit exceeded
30 Halted 0 ms 0 KB -