oj.uz

Submission #912044

# Submission time Handle Problem Language Result Execution time Memory
912044 2024-01-19T07:10:24 Z winter0101 Stray Cat (JOI20_stray) C++14
15 / 100
 54 ms 17628 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;
vector<int>a[maxn];
vector<pii>g[maxn];
bool vis[maxn];
int d[maxn];
int b[6]={0,1,0,0,1,1};
vector<int>id;
int msk[maxn];
int xr=1;
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 lst=0;
for1(i,0,sz(id)-1){
msk[id[i]]=(b[i%6]^xr);
lst=msk[id[i]];
}
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];
  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;

}  // 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-4+1){
  int cc=0,sum=0;
  for1(j,i,i+3){
  sum+=c[j]*(1<<cc);
  cc++;
  }
  patt.insert(sum);
  }
}
int cnt[3];
bool detact=false;
int lst=-1;
vector<int>xx;
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;
  }
  }
  }
  //
  if (!detact){
  step++;
  int deg=0;
  for1(i,0,A-1){
  deg+=y[i];
  }
  if (deg==1){
  for1(i,0,A-1){
  if (y[i]!=0){
  xx.pb(i);
  lst=i;
  return i;
  }
  }
  }
  else if (deg==0){
  step--;
  lst=xx.back();
  xx.pop_back();
  detact=1;
  return -1;
  }
  deg+=(step>1);
  if (deg==2){
  for1(i,0,A-1){
  if (y[i]!=0){
  xx.pb(i);
  lst=i;
  return i;
  }
  }
  }
  if (deg>2){
  if (lst!=-1)y[lst]++;
  if (y[lst]==1){
  lst=xx.back();
  xx.pop_back();
  detact=1;
  step--;
  return -1;
  }
  step=0;
  detact=1;
  for1(i,0,A-1){
  if (y[i]==1){
  lst=i;
  return i;
  }
  }
  }
  }
  else {
  if (step){
  lst=xx.back();
  xx.pop_back();
  step--;
  return -1;
  }
  else {
  int deg=0;
  for1(i,0,A-1){
  deg+=y[i];
  }
  if (deg==1){
  for1(i,0,A-1)if (y[i]!=0)return i;
  }
  else {
  if (lst!=-1)y[lst]++;
  for1(i,0,A-1)if (y[i]==1)return i;
  }
  }
  }

}

Compilation message

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

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

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 16372 KB Output is correct
2 Correct 1 ms 1808 KB Output is correct
3 Correct 26 ms 15924 KB Output is correct
4 Correct 40 ms 17628 KB Output is correct
5 Correct 41 ms 17608 KB Output is correct
6 Correct 34 ms 16112 KB Output is correct
7 Correct 38 ms 16164 KB Output is correct
8 Correct 44 ms 16716 KB Output is correct
9 Correct 35 ms 16932 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 16372 KB Output is correct
2 Correct 1 ms 1808 KB Output is correct
3 Correct 26 ms 15924 KB Output is correct
4 Correct 40 ms 17628 KB Output is correct
5 Correct 41 ms 17608 KB Output is correct
6 Correct 34 ms 16112 KB Output is correct
7 Correct 38 ms 16164 KB Output is correct
8 Correct 44 ms 16716 KB Output is correct
9 Correct 35 ms 16932 KB Output is correct
10 Correct 27 ms 14384 KB Output is correct
11 Correct 31 ms 14396 KB Output is correct
12 Correct 31 ms 14364 KB Output is correct
13 Correct 30 ms 14288 KB Output is correct
14 Correct 28 ms 14664 KB Output is correct
15 Correct 33 ms 14828 KB Output is correct
16 Correct 54 ms 16896 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 14020 KB Output is correct
2 Correct 1 ms 1812 KB Output is correct
3 Correct 28 ms 13688 KB Output is correct
4 Correct 53 ms 15436 KB Output is correct
5 Correct 48 ms 15204 KB Output is correct
6 Correct 28 ms 13816 KB Output is correct
7 Correct 39 ms 13884 KB Output is correct
8 Correct 43 ms 15104 KB Output is correct
9 Correct 38 ms 14672 KB Output is correct
10 Correct 36 ms 14640 KB Output is correct
11 Correct 43 ms 14444 KB Output is correct
12 Correct 42 ms 14172 KB Output is correct
13 Correct 33 ms 14404 KB Output is correct
14 Correct 38 ms 14664 KB Output is correct
15 Correct 46 ms 14580 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 14020 KB Output is correct
2 Correct 1 ms 1812 KB Output is correct
3 Correct 28 ms 13688 KB Output is correct
4 Correct 53 ms 15436 KB Output is correct
5 Correct 48 ms 15204 KB Output is correct
6 Correct 28 ms 13816 KB Output is correct
7 Correct 39 ms 13884 KB Output is correct
8 Correct 43 ms 15104 KB Output is correct
9 Correct 38 ms 14672 KB Output is correct
10 Correct 36 ms 14640 KB Output is correct
11 Correct 43 ms 14444 KB Output is correct
12 Correct 42 ms 14172 KB Output is correct
13 Correct 33 ms 14404 KB Output is correct
14 Correct 38 ms 14664 KB Output is correct
15 Correct 46 ms 14580 KB Output is correct
16 Correct 26 ms 12276 KB Output is correct
17 Correct 26 ms 12272 KB Output is correct
18 Correct 30 ms 12336 KB Output is correct
19 Correct 32 ms 12364 KB Output is correct
20 Correct 47 ms 13024 KB Output is correct
21 Correct 37 ms 12664 KB Output is correct
22 Correct 53 ms 14712 KB Output is correct
23 Correct 33 ms 12528 KB Output is correct
24 Correct 29 ms 12588 KB Output is correct

Subtask #5
0 / 5.0

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

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 12096 KB Wrong Answer [5]
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 12276 KB Wrong Answer [3]
2 Halted 0 ms 0 KB -