oj.uz

Submission #912130

# Submission time Handle Problem Language Result Execution time Memory
912130 2024-01-19T07:46:48 Z winter0101 Stray Cat (JOI20_stray) C++14
15 / 100
 39 ms 16992 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];
  //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-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;
  }
  }
  }
  //
  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 (deg>=3&&!detact){
  step=0;
  detact=1;
  }
  int gg=0;
  for1(i,0,A-1){
  gg+=y[i];
  }
  if (gg==0){
  detact=1;
  }
  if (!detact){
  step++;
  for1(i,0,A-1){
  if (y[i]!=0){
  xx.pb(i);
  lst=i;
  return i;
  }
  }
  }
  else {
  if (step){
  lst=xx.back();
  xx.pop_back();
  step=0;
  return -1;
  }
  else {
  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: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:141:1: warning: control reaches end of non-void function [-Wreturn-type]
  141 | }
      | ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 15984 KB Output is correct
2 Correct 1 ms 1816 KB Output is correct
3 Correct 26 ms 15484 KB Output is correct
4 Correct 39 ms 16992 KB Output is correct
5 Correct 36 ms 16944 KB Output is correct
6 Correct 32 ms 15780 KB Output is correct
7 Correct 28 ms 15740 KB Output is correct
8 Correct 32 ms 16508 KB Output is correct
9 Correct 36 ms 16628 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 15984 KB Output is correct
2 Correct 1 ms 1816 KB Output is correct
3 Correct 26 ms 15484 KB Output is correct
4 Correct 39 ms 16992 KB Output is correct
5 Correct 36 ms 16944 KB Output is correct
6 Correct 32 ms 15780 KB Output is correct
7 Correct 28 ms 15740 KB Output is correct
8 Correct 32 ms 16508 KB Output is correct
9 Correct 36 ms 16628 KB Output is correct
10 Correct 26 ms 13844 KB Output is correct
11 Correct 26 ms 13940 KB Output is correct
12 Correct 28 ms 13920 KB Output is correct
13 Correct 28 ms 13936 KB Output is correct
14 Correct 27 ms 14128 KB Output is correct
15 Correct 30 ms 14432 KB Output is correct
16 Correct 32 ms 16508 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 13440 KB Output is correct
2 Correct 1 ms 1804 KB Output is correct
3 Correct 24 ms 13180 KB Output is correct
4 Correct 38 ms 14980 KB Output is correct
5 Correct 39 ms 14876 KB Output is correct
6 Correct 28 ms 13344 KB Output is correct
7 Correct 28 ms 13344 KB Output is correct
8 Correct 33 ms 14168 KB Output is correct
9 Correct 32 ms 14180 KB Output is correct
10 Correct 30 ms 13940 KB Output is correct
11 Correct 30 ms 13948 KB Output is correct
12 Correct 31 ms 13944 KB Output is correct
13 Correct 30 ms 13840 KB Output is correct
14 Correct 32 ms 14376 KB Output is correct
15 Correct 32 ms 14132 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 13440 KB Output is correct
2 Correct 1 ms 1804 KB Output is correct
3 Correct 24 ms 13180 KB Output is correct
4 Correct 38 ms 14980 KB Output is correct
5 Correct 39 ms 14876 KB Output is correct
6 Correct 28 ms 13344 KB Output is correct
7 Correct 28 ms 13344 KB Output is correct
8 Correct 33 ms 14168 KB Output is correct
9 Correct 32 ms 14180 KB Output is correct
10 Correct 30 ms 13940 KB Output is correct
11 Correct 30 ms 13948 KB Output is correct
12 Correct 31 ms 13944 KB Output is correct
13 Correct 30 ms 13840 KB Output is correct
14 Correct 32 ms 14376 KB Output is correct
15 Correct 32 ms 14132 KB Output is correct
16 Correct 24 ms 11888 KB Output is correct
17 Correct 25 ms 11888 KB Output is correct
18 Correct 28 ms 11976 KB Output is correct
19 Correct 27 ms 11896 KB Output is correct
20 Correct 28 ms 12800 KB Output is correct
21 Correct 27 ms 12408 KB Output is correct
22 Correct 31 ms 14392 KB Output is correct
23 Correct 27 ms 12152 KB Output is correct
24 Correct 26 ms 12384 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2072 KB Output is correct
2 Correct 1 ms 1824 KB Output is correct
3 Correct 3 ms 2080 KB Output is correct
4 Correct 2 ms 2076 KB Output is correct
5 Correct 2 ms 2084 KB Output is correct
6 Correct 2 ms 2084 KB Output is correct
7 Correct 2 ms 2076 KB Output is correct
8 Correct 2 ms 2084 KB Output is correct
9 Correct 2 ms 2080 KB Output is correct
10 Correct 3 ms 2228 KB Output is correct
11 Correct 2 ms 2084 KB Output is correct
12 Correct 2 ms 2080 KB Output is correct
13 Correct 2 ms 2076 KB Output is correct
14 Incorrect 2 ms 2092 KB Wrong Answer [5]
15 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 11900 KB Output is correct
2 Correct 27 ms 13392 KB Output is correct
3 Correct 1 ms 1812 KB Output is correct
4 Correct 26 ms 12068 KB Output is correct
5 Correct 33 ms 15100 KB Output is correct
6 Correct 33 ms 15076 KB Output is correct
7 Incorrect 28 ms 14156 KB Wrong Answer [6]
8 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 11896 KB Output is correct
2 Incorrect 28 ms 13196 KB Wrong Answer [5]
3 Halted 0 ms 0 KB -