oj.uz

Submission #912308

# Submission time Handle Problem Language Result Execution time Memory
912308 2024-01-19T09:52:46 Z winter0101 Stray Cat (JOI20_stray) C++14
100 / 100
 47 ms 17008 KB 
#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
const int maxn=2e4+9;
//pattern la 010011 thi voi moi cyclic thi dao nguoc deu khong co
vector<int>a[maxn];
vector<pii>g[maxn];
bool vis[maxn];
int d[maxn];
int b[12]={0,1,0,0,1,1,0,1,0,0,1,1};
vector<int>id;
int msk[maxn];
int xr=0;
void dfs(int u,int par){
int cnt=0;
for (auto v:g[u]){
if (v.fi==par)continue;
cnt++;
}
if (cnt>1||cnt==0){
int nw=0;
for1(i,0,11){
if (xr==b[i]){
nw=i;
break;
}
}
int lst=0;
for1(i,0,sz(id)-1){
msk[id[i]]=b[nw];
lst=msk[id[i]];
nw=(nw+1)%12;
}
id.clear();
xr=(lst^1);
}
int xd=xr;
for (auto v:g[u]){
if (v.fi==par)continue;
id.pb(v.se);
dfs(v.fi,u);
xr=xd;
}
}
std::vector<int> Mark(int N, int M, int A, int B,std::vector<int> U, std::vector<int> V) {
  int n=N,m=M;
  if (B==0){
  std::vector<int> x(M);
  for1(i,0,m-1){
  a[U[i]].pb(V[i]);
  a[V[i]].pb(U[i]);
  }
  vis[0]=1;
  queue<int>t;
  t.push(0);
  while (!t.empty()){
  auto u=t.front();
  t.pop();
  for (auto v:a[u]){
  if (vis[v])continue;
  d[v]=d[u]+1;
  t.push(v);
  vis[v]=1;
  }
  }
  for (int i = 0; i < M; ++i) {
  int u=U[i],v=V[i];
  if (d[u]==d[v]){
  int t1=(d[u]%3),t2=(t1+1)%3;
  if (t1==1||t2==1)x[i]|=(1<<0);
  if (t1==2||t2==2)x[i]|=(1<<1);
  x[i]--;
  continue;
  }
  if (d[u]>d[v])swap(u,v);
  int mask=0;
  if (d[u]%3==2||d[v]%3==2)mask|=(1<<1);
  if (d[u]%3==1||d[v]%3==1)mask|=(1<<0);
  x[i]=mask-1;
  }
  return x;
  }
  else {
  for1(i,0,m-1){
  g[U[i]].pb({V[i],i});
  g[V[i]].pb({U[i],i});
  }
  dfs(0,0);
  vector<int>x(M);
  for1(i,0,m-1)x[i]=msk[i];
  //for1(i,0,m-1)cout<<U[i]<<" "<<V[i]<<" "<<x[i]<<'\n';
  return x;
  }
}
#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
namespace {
 
int A, B;
int step = 0;
int nw=0;
}  // namespace
int c[12]={0,1,0,0,1,1,0,1,0,0,1,1};
set<int>patt;
void Init(int A, int B) {
  ::A = A;
  ::B = B;
  if (B==0){
  return;
  }
  for1(i,0,11-5+1){
  int cc=0,sum=0;
  for1(j,i,i+4){
  sum+=c[j]*(1<<cc);
  cc++;
  }
  patt.insert(sum);
  }
}
int cnt[3];
bool detact=false;
int lst=-1;
vector<int>xx,yy;
int Move(std::vector<int> y) {
  //
  if (B==0){
  int ct=0;
  for1(i,0,2){
  if (y[i]!=0)ct++;
  }
  if (ct==1){
  for1(i,0,2){
  if (y[i]!=0)return i;
  }
  }
  for1(i,0,2)cnt[i]=0;
  for1(i,0,2){
  if (y[i]!=0){
  int j=i+1;
  for1(k,0,1){
  if (j>>k&1){
  cnt[(1<<k)]++;
  }
  else {
  cnt[0]++;
  }
  }
  }
  }
  for1(i,0,2){
  if (cnt[i]==2){
  int ans=i;
  int gg=(i-1+3)%3;
  ans+=gg;
  return ans-1;
  }
  }
  }
  //
  nw++;
  /*cout<<"STEP "<<nw<<'\n';
  for1(i,0,A-1)cout<<y[i]<<" ";
  cout<<'\n';*/
  int deg=(nw>1);
  for1(i,0,A-1)deg+=y[i];
  if (nw==1&&deg>=3){
  for1(i,0,A-1){
  if (y[i]==1){
  lst=i;
  detact=1;
  return i;
  }
  }
  }
  if (nw==1&&deg==1){
  step=0;
  detact=1;
  xx.clear();
  for1(i,0,A-1){
  if (y[i]==1){
  lst=i;
  return i;
  }
  }
  }
  //cerr<<deg<<" "<<detact<<'\n';
  if (deg>=3&&!detact){
  if (lst!=-1)y[lst]++;
  detact=1;
  for1(i,0,A-1){
  if (y[i]==1){
  if (i==lst){
  lst=xx.back();
  xx.pop_back();
  step=0;
  return -1;
  }
  xx.clear();
  step=0;
  lst=i;
  return i;
  }
  }
  }
  int gg=0;
  for1(i,0,A-1){
  gg+=y[i];
  }
  if (gg==0){
  detact=1;
  }
  //cerr<<"STEP "<<nw<<" "<<detact<<" "<<sz(xx)<<'\n';
  if (!detact){
  step++;
  for1(i,0,A-1){
  for1(j,1,y[i]){
  yy.pb(i);
  }
  }
  if (nw<4){
  lst=yy.back();
  xx.pb(lst);
  return yy.back();
  }
  if (step==4){
  int mk=0;
  for1(i,0,4){
  mk+=yy[i]*(1<<i);
  }
  if (patt.find(mk)==patt.end()){
  step=0;
  detact=1;
  xx.clear();
  }
  else {
  detact=1;
  }
  }
  }
  //cerr<<"STEP "<<detact<<" "<<sz(xx)<<'\n';
  //cerr<<"check "<<detact<<'\n';
  if (detact) {
  if (step){
  lst=xx.back();
  xx.pop_back();
  step=0;
  return -1;
  }
  else {
  if (!xx.empty()){
  lst=xx.back();
  xx.pop_back();
  return lst;
  }
  if (gg==1){
  for1(i,0,A-1){
  if (y[i]==1){
  lst=i;
  return i;
  }
  }
  }
  if (lst!=-1)y[lst]++;
  for1(i,0,A-1){
  if (y[i]==1){
  lst=i;
  return i;
  }
  }
  }
  }
}

Compilation message

Anthony.cpp: In function 'std::vector<int> Mark(int, int, int, int, std::vector<int>, std::vector<int>)':
Anthony.cpp:59:7: warning: unused variable 'n' [-Wunused-variable]
   59 |   int n=N,m=M;
      |       ^

Catherine.cpp: In function 'int Move(std::vector<int>)':
Catherine.cpp:192:1: warning: control reaches end of non-void function [-Wreturn-type]
  192 | }
      | ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 15888 KB Output is correct
2 Correct 1 ms 1804 KB Output is correct
3 Correct 30 ms 15480 KB Output is correct
4 Correct 34 ms 17008 KB Output is correct
5 Correct 38 ms 16904 KB Output is correct
6 Correct 28 ms 15736 KB Output is correct
7 Correct 30 ms 15764 KB Output is correct
8 Correct 34 ms 16472 KB Output is correct
9 Correct 36 ms 16680 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 15888 KB Output is correct
2 Correct 1 ms 1804 KB Output is correct
3 Correct 30 ms 15480 KB Output is correct
4 Correct 34 ms 17008 KB Output is correct
5 Correct 38 ms 16904 KB Output is correct
6 Correct 28 ms 15736 KB Output is correct
7 Correct 30 ms 15764 KB Output is correct
8 Correct 34 ms 16472 KB Output is correct
9 Correct 36 ms 16680 KB Output is correct
10 Correct 32 ms 13880 KB Output is correct
11 Correct 26 ms 13932 KB Output is correct
12 Correct 26 ms 13940 KB Output is correct
13 Correct 27 ms 13940 KB Output is correct
14 Correct 27 ms 14160 KB Output is correct
15 Correct 30 ms 14452 KB Output is correct
16 Correct 36 ms 16420 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 13504 KB Output is correct
2 Correct 1 ms 1820 KB Output is correct
3 Correct 24 ms 13156 KB Output is correct
4 Correct 33 ms 14972 KB Output is correct
5 Correct 34 ms 14896 KB Output is correct
6 Correct 27 ms 13348 KB Output is correct
7 Correct 27 ms 13432 KB Output is correct
8 Correct 33 ms 14424 KB Output is correct
9 Correct 31 ms 14228 KB Output is correct
10 Correct 28 ms 13932 KB Output is correct
11 Correct 34 ms 14208 KB Output is correct
12 Correct 30 ms 13968 KB Output is correct
13 Correct 33 ms 13820 KB Output is correct
14 Correct 33 ms 14156 KB Output is correct
15 Correct 32 ms 14228 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 13504 KB Output is correct
2 Correct 1 ms 1820 KB Output is correct
3 Correct 24 ms 13156 KB Output is correct
4 Correct 33 ms 14972 KB Output is correct
5 Correct 34 ms 14896 KB Output is correct
6 Correct 27 ms 13348 KB Output is correct
7 Correct 27 ms 13432 KB Output is correct
8 Correct 33 ms 14424 KB Output is correct
9 Correct 31 ms 14228 KB Output is correct
10 Correct 28 ms 13932 KB Output is correct
11 Correct 34 ms 14208 KB Output is correct
12 Correct 30 ms 13968 KB Output is correct
13 Correct 33 ms 13820 KB Output is correct
14 Correct 33 ms 14156 KB Output is correct
15 Correct 32 ms 14228 KB Output is correct
16 Correct 24 ms 11912 KB Output is correct
17 Correct 25 ms 11948 KB Output is correct
18 Correct 28 ms 11868 KB Output is correct
19 Correct 26 ms 11988 KB Output is correct
20 Correct 37 ms 12664 KB Output is correct
21 Correct 27 ms 12468 KB Output is correct
22 Correct 31 ms 14468 KB Output is correct
23 Correct 26 ms 12192 KB Output is correct
24 Correct 27 ms 12196 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2096 KB Output is correct
2 Correct 1 ms 1832 KB Output is correct
3 Correct 2 ms 2088 KB Output is correct
4 Correct 2 ms 1932 KB Output is correct
5 Correct 2 ms 2104 KB Output is correct
6 Correct 2 ms 2092 KB Output is correct
7 Correct 2 ms 2096 KB Output is correct
8 Correct 2 ms 2076 KB Output is correct
9 Correct 2 ms 2076 KB Output is correct
10 Correct 2 ms 2064 KB Output is correct
11 Correct 2 ms 2068 KB Output is correct
12 Correct 2 ms 2072 KB Output is correct
13 Correct 2 ms 2072 KB Output is correct
14 Correct 2 ms 2076 KB Output is correct
15 Correct 2 ms 2072 KB Output is correct
16 Correct 2 ms 2076 KB Output is correct
17 Correct 2 ms 2080 KB Output is correct
18 Correct 2 ms 2032 KB Output is correct
19 Correct 2 ms 2072 KB Output is correct
20 Correct 3 ms 2076 KB Output is correct
21 Correct 2 ms 2080 KB Output is correct
22 Correct 2 ms 2080 KB Output is correct
23 Correct 2 ms 2076 KB Output is correct
24 Correct 2 ms 2080 KB Output is correct
25 Correct 2 ms 2076 KB Output is correct
26 Correct 2 ms 2080 KB Output is correct
27 Correct 2 ms 2080 KB Output is correct
28 Correct 2 ms 2064 KB Output is correct

Subtask #6
71.0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 11888 KB Output is correct
2 Correct 28 ms 13136 KB Output is correct
3 Correct 1 ms 1808 KB Output is correct
4 Correct 24 ms 11632 KB Output is correct
5 Correct 34 ms 14704 KB Output is correct
6 Correct 40 ms 14624 KB Output is correct
7 Correct 31 ms 13848 KB Output is correct
8 Correct 27 ms 13692 KB Output is correct
9 Correct 34 ms 14884 KB Output is correct
10 Correct 34 ms 14708 KB Output is correct
11 Correct 31 ms 14720 KB Output is correct
12 Correct 34 ms 14684 KB Output is correct
13 Correct 33 ms 14588 KB Output is correct
14 Correct 33 ms 14704 KB Output is correct
15 Correct 47 ms 14708 KB Output is correct
16 Correct 34 ms 14628 KB Output is correct
17 Correct 28 ms 14460 KB Output is correct
18 Correct 34 ms 14368 KB Output is correct
19 Correct 30 ms 14464 KB Output is correct
20 Correct 31 ms 14364 KB Output is correct
21 Correct 28 ms 14320 KB Output is correct
22 Correct 28 ms 14472 KB Output is correct
23 Correct 25 ms 11900 KB Output is correct
24 Correct 28 ms 11936 KB Output is correct
25 Correct 27 ms 12340 KB Output is correct
26 Correct 28 ms 12412 KB Output is correct
27 Correct 32 ms 13092 KB Output is correct
28 Correct 30 ms 13280 KB Output is correct
29 Correct 30 ms 13088 KB Output is correct
30 Correct 31 ms 13176 KB Output is correct
31 Correct 33 ms 11888 KB Output is correct
32 Correct 32 ms 11856 KB Output is correct
33 Correct 27 ms 12412 KB Output is correct
34 Correct 30 ms 12404 KB Output is correct
35 Correct 44 ms 12832 KB Output is correct
36 Correct 32 ms 12916 KB Output is correct
37 Correct 38 ms 13048 KB Output is correct
38 Correct 30 ms 12924 KB Output is correct
39 Correct 30 ms 12880 KB Output is correct
40 Correct 32 ms 12924 KB Output is correct
41 Correct 44 ms 13640 KB Output is correct
42 Correct 31 ms 13940 KB Output is correct
43 Correct 35 ms 13524 KB Output is correct
44 Correct 41 ms 13772 KB Output is correct
45 Correct 33 ms 14016 KB Output is correct
46 Correct 34 ms 13688 KB Output is correct
47 Correct 40 ms 12796 KB Output is correct
48 Correct 34 ms 12616 KB Output is correct
49 Correct 34 ms 12648 KB Output is correct
50 Correct 33 ms 12872 KB Output is correct
51 Correct 25 ms 11876 KB Output is correct
52 Correct 28 ms 11880 KB Output is correct
53 Correct 31 ms 11920 KB Output is correct
54 Correct 27 ms 11892 KB Output is correct
55 Correct 27 ms 11920 KB Output is correct
56 Correct 33 ms 11912 KB Output is correct
57 Correct 35 ms 11824 KB Output is correct
58 Correct 34 ms 12036 KB Output is correct
59 Correct 28 ms 11888 KB Output is correct
60 Correct 30 ms 11880 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 11880 KB Output is correct
2 Correct 27 ms 12868 KB Output is correct
3 Correct 1 ms 1808 KB Output is correct
4 Correct 26 ms 11640 KB Output is correct
5 Correct 45 ms 14668 KB Output is correct
6 Correct 41 ms 14664 KB Output is correct
7 Correct 28 ms 13700 KB Output is correct
8 Correct 34 ms 13852 KB Output is correct
9 Correct 45 ms 14652 KB Output is correct
10 Correct 39 ms 14716 KB Output is correct
11 Correct 39 ms 14620 KB Output is correct
12 Correct 33 ms 14636 KB Output is correct
13 Correct 37 ms 14724 KB Output is correct
14 Correct 35 ms 14620 KB Output is correct
15 Correct 43 ms 14708 KB Output is correct
16 Correct 30 ms 14712 KB Output is correct
17 Correct 30 ms 14420 KB Output is correct
18 Correct 31 ms 14460 KB Output is correct
19 Correct 28 ms 14460 KB Output is correct
20 Correct 30 ms 14460 KB Output is correct
21 Correct 36 ms 14404 KB Output is correct
22 Correct 32 ms 14452 KB Output is correct
23 Correct 26 ms 12288 KB Output is correct
24 Correct 26 ms 11888 KB Output is correct
25 Correct 28 ms 12404 KB Output is correct
26 Correct 26 ms 12408 KB Output is correct
27 Correct 30 ms 13136 KB Output is correct
28 Correct 28 ms 13188 KB Output is correct
29 Correct 36 ms 13380 KB Output is correct
30 Correct 28 ms 13192 KB Output is correct
31 Correct 25 ms 11908 KB Output is correct
32 Correct 33 ms 11936 KB Output is correct
33 Correct 27 ms 12412 KB Output is correct
34 Correct 27 ms 12528 KB Output is correct
35 Correct 34 ms 12920 KB Output is correct
36 Correct 28 ms 12928 KB Output is correct
37 Correct 28 ms 12924 KB Output is correct
38 Correct 28 ms 12904 KB Output is correct
39 Correct 40 ms 12836 KB Output is correct
40 Correct 28 ms 12928 KB Output is correct
41 Correct 30 ms 13692 KB Output is correct
42 Correct 31 ms 13700 KB Output is correct
43 Correct 36 ms 13688 KB Output is correct
44 Correct 28 ms 13692 KB Output is correct
45 Correct 38 ms 13800 KB Output is correct
46 Correct 28 ms 13624 KB Output is correct
47 Correct 28 ms 12968 KB Output is correct
48 Correct 32 ms 12912 KB Output is correct
49 Correct 27 ms 12732 KB Output is correct
50 Correct 27 ms 12944 KB Output is correct
51 Correct 27 ms 11892 KB Output is correct
52 Correct 28 ms 12024 KB Output is correct
53 Correct 27 ms 12000 KB Output is correct
54 Correct 26 ms 11892 KB Output is correct
55 Correct 25 ms 11888 KB Output is correct
56 Correct 25 ms 11908 KB Output is correct
57 Correct 26 ms 11872 KB Output is correct
58 Correct 25 ms 11892 KB Output is correct
59 Correct 26 ms 11852 KB Output is correct
60 Correct 31 ms 12020 KB Output is correct