oj.uz

Submission #829719

# Submission time Handle Problem Language Result Execution time Memory
829719 2023-08-18T14:27:23 Z NemanjaSo2005 Stray Cat (JOI20_stray) C++17
15 / 100
 34 ms 16668 KB 
#include "Anthony.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
vector<int> graf[20005];
int dist[20005],sta[20005];
queue<int> Q;
string E;
int N;
bool prosli[20005];
void BFS(int gde){
   for(int i=0;i<=N;i++)
      dist[i]=-1;
   dist[gde]=0;
   Q.push(gde);
   while(Q.size()){
      int tren=Q.front();
      Q.pop();
      if(prosli[tren])
         continue;
      //cout<<tren<<endl;
      prosli[tren]=true;
      for(int i=0;i<graf[tren].size();i++)
         if(dist[graf[tren][i]]==-1){
            dist[graf[tren][i]]=dist[tren]+1;
            Q.push(graf[tren][i]);
         }
   }
   return;
}
void dfs2(int gde,int pret,int cyc){
   if(gde==pret)
      for(int i=0;i<graf[gde].size();i++){
         dfs2(graf[gde][i],gde,0);
         return;
      }
   if(cyc==16)
      sta[gde]=0;
   if(cyc==32)
      sta[gde]=1;
   if(cyc<=5)
      sta[gde]=E[cyc]-'0';
   if(graf[gde].size()>2){
      if(sta[gde]==1)
         cyc=16;
      else
         cyc=32;
      for(int i=0;i<graf[gde].size();i++){
         if(graf[gde][i]!=pret)
            dfs2(graf[gde][i],gde,cyc);
      }
      return;
   }
   if(cyc>=16)
      for(int i=0;i<E.size();i++)
         if(E[i]==sta[gde]+'0'){
            cyc=i;
         }
   cyc++;
   if(cyc==6)
      cyc=0;
   for(int i=0;i<graf[gde].size();i++)
      if(graf[gde][i]!=pret)
         dfs2(graf[gde][i],gde,cyc);
   return;
}
vector<int> Mark(int n, int M, int A, int B, vector<int> U,vector<int> V) {
   N=n;
   for(int i=0;i<M;i++){
      graf[U[i]].push_back(V[i]);
      graf[V[i]].push_back(U[i]);
   }
   BFS(0);
   /*for(int i=0;i<N;i++)
      cout<<dist[i]<<" ";
   cout<<endl;*/
   if(A==2){
      E="001011";
      vector<int> R;
      dfs2(0,0,-1);
      for(int i=0;i<M;i++){
         int koj;
         if(dist[U[i]]>dist[V[i]])
            koj=U[i];
         else
            koj=V[i];
         R.push_back(sta[koj]);
      }
      return R;
   }
   string S="012";
   vector<int> R;
   for(int i=0;i<M;i++){
      int md=min(dist[U[i]],dist[V[i]]);
      R.push_back(S[md%3]-'0');
   }
   return R;
}
#include "Catherine.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int slucaj,nalazi=0;
set<string> S;
void Init(int A, int B) {
   if(A==2){
      slucaj=2;
      string x="001011";
      x+=x;
      x+=x;
      for(int i=0;i+4<x.size();i++)
         S.insert(x.substr(i,5));
   }
   else
      slucaj=1;
}
bool prvipot=true;
string T;
int Move(std::vector<int> y) {
   if(slucaj==1){
      if(y[0]==0 and y[1]==0)
         return 2;
      if(y[0]==0 and y[2]==0)
         return 1;
      if(y[1]==0 and y[2]==0)
         return 0;
      if(y[0]==0)
         return 1;
      if(y[1]==0)
         return 2;
      return 0;
   }
  // cout<<"POTEZ "<<y[0]<<" "<<y[1]<<endl;
   if(0==y[0] and y[1]==0){
      nalazi=4;
      prvipot=false;
      return -1;
   }
   if(y[0]>y[1] and y[0]>1+prvipot){
      nalazi=4;
      prvipot=false;
      if(y[1]!=0)
         return 1;
      else
         return -1;
   }
   if(y[0]<y[1] and y[1]>1+prvipot){
      nalazi=4;
      prvipot=false;
      if(y[0]!=0)
         return 0;
      else
         return -1;
   }
   if(nalazi==0){
      prvipot=false;
      if(y[0]==0 and y[1]==1){
         nalazi=4;
         return 1;
      }
      if(y[1]==0 and y[0]==1){
         nalazi=4;
         return 0;
      }
      nalazi++;
      if(y[0]==2){
         T+="00";
         return 0;
      }
      if(y[1]==2){
         T+="11";
         return 1;
      }
      T+="01";
      return 1;
   }
   if(nalazi==1 or nalazi==2){
      if(y[0]==1){
         T+="0";
         nalazi++;
         return 0;
      }
      T+="1";
      nalazi++;
      return 1;
   }
   if(nalazi==3){
      if(y[0]==1)
         T+="0";
      else
         T+="1";
      //cout<<T<<endl;
      nalazi++;
      if(S.find(T)!=S.end()){
        // cout<<"LOSE"<<endl;
         return -1;
      }
      if(y[0]==1)
         return 0;
      return 1;
   }
   if(y[0]==0){
      nalazi=4;
      return 1;
   }
   if(y[1]==0){
      return 0;
   }
   return -1;
}

Compilation message

Anthony.cpp: In function 'void BFS(int)':
Anthony.cpp:23:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |       for(int i=0;i<graf[tren].size();i++)
      |                   ~^~~~~~~~~~~~~~~~~~
Anthony.cpp: In function 'void dfs2(int, int, int)':
Anthony.cpp:33:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |       for(int i=0;i<graf[gde].size();i++){
      |                   ~^~~~~~~~~~~~~~~~~
Anthony.cpp:48:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |       for(int i=0;i<graf[gde].size();i++){
      |                   ~^~~~~~~~~~~~~~~~~
Anthony.cpp:55:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |       for(int i=0;i<E.size();i++)
      |                   ~^~~~~~~~~
Anthony.cpp:62:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |    for(int i=0;i<graf[gde].size();i++)
      |                ~^~~~~~~~~~~~~~~~~

Catherine.cpp: In function 'void Init(int, int)':
Catherine.cpp:13:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |       for(int i=0;i+4<x.size();i++)
      |                   ~~~^~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 15516 KB Output is correct
2 Correct 1 ms 1064 KB Output is correct
3 Correct 23 ms 14820 KB Output is correct
4 Correct 32 ms 16616 KB Output is correct
5 Correct 32 ms 16668 KB Output is correct
6 Correct 27 ms 15288 KB Output is correct
7 Correct 33 ms 15456 KB Output is correct
8 Correct 33 ms 15848 KB Output is correct
9 Correct 30 ms 15904 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 15516 KB Output is correct
2 Correct 1 ms 1064 KB Output is correct
3 Correct 23 ms 14820 KB Output is correct
4 Correct 32 ms 16616 KB Output is correct
5 Correct 32 ms 16668 KB Output is correct
6 Correct 27 ms 15288 KB Output is correct
7 Correct 33 ms 15456 KB Output is correct
8 Correct 33 ms 15848 KB Output is correct
9 Correct 30 ms 15904 KB Output is correct
10 Correct 28 ms 13416 KB Output is correct
11 Correct 30 ms 13316 KB Output is correct
12 Correct 25 ms 13416 KB Output is correct
13 Correct 25 ms 13380 KB Output is correct
14 Correct 25 ms 13532 KB Output is correct
15 Correct 27 ms 14064 KB Output is correct
16 Correct 31 ms 16096 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 13120 KB Output is correct
2 Correct 0 ms 1032 KB Output is correct
3 Correct 23 ms 12640 KB Output is correct
4 Correct 31 ms 14432 KB Output is correct
5 Correct 32 ms 14340 KB Output is correct
6 Correct 30 ms 13164 KB Output is correct
7 Correct 26 ms 13116 KB Output is correct
8 Correct 28 ms 13668 KB Output is correct
9 Correct 30 ms 13872 KB Output is correct
10 Correct 30 ms 13552 KB Output is correct
11 Correct 27 ms 13492 KB Output is correct
12 Correct 27 ms 13584 KB Output is correct
13 Correct 34 ms 13484 KB Output is correct
14 Correct 34 ms 13808 KB Output is correct
15 Correct 27 ms 13724 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 13120 KB Output is correct
2 Correct 0 ms 1032 KB Output is correct
3 Correct 23 ms 12640 KB Output is correct
4 Correct 31 ms 14432 KB Output is correct
5 Correct 32 ms 14340 KB Output is correct
6 Correct 30 ms 13164 KB Output is correct
7 Correct 26 ms 13116 KB Output is correct
8 Correct 28 ms 13668 KB Output is correct
9 Correct 30 ms 13872 KB Output is correct
10 Correct 30 ms 13552 KB Output is correct
11 Correct 27 ms 13492 KB Output is correct
12 Correct 27 ms 13584 KB Output is correct
13 Correct 34 ms 13484 KB Output is correct
14 Correct 34 ms 13808 KB Output is correct
15 Correct 27 ms 13724 KB Output is correct
16 Correct 22 ms 11500 KB Output is correct
17 Correct 23 ms 11488 KB Output is correct
18 Correct 23 ms 11532 KB Output is correct
19 Correct 24 ms 11484 KB Output is correct
20 Correct 26 ms 12144 KB Output is correct
21 Correct 25 ms 11812 KB Output is correct
22 Correct 28 ms 13896 KB Output is correct
23 Correct 24 ms 11632 KB Output is correct
24 Correct 25 ms 11644 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1288 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 10796 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 10860 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -