oj.uz

답안 #912158

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
912158 2024-01-19T07:54:10 Z winter0101 길고양이 (JOI20_stray) C++14
20 / 100
 46 ms 17164 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){
  if (lst!=-1)y[lst]++;
  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;
  }
  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 (!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: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:159:1: warning: control reaches end of non-void function [-Wreturn-type]
  159 | }
      | ^

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 15768 KB Output is correct
2 Correct 1 ms 1804 KB Output is correct
3 Correct 25 ms 15476 KB Output is correct
4 Correct 41 ms 17164 KB Output is correct
5 Correct 38 ms 17012 KB Output is correct
6 Correct 30 ms 15732 KB Output is correct
7 Correct 27 ms 15880 KB Output is correct
8 Correct 41 ms 16436 KB Output is correct
9 Correct 33 ms 16424 KB Output is correct

Subtask #2
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 15768 KB Output is correct
2 Correct 1 ms 1804 KB Output is correct
3 Correct 25 ms 15476 KB Output is correct
4 Correct 41 ms 17164 KB Output is correct
5 Correct 38 ms 17012 KB Output is correct
6 Correct 30 ms 15732 KB Output is correct
7 Correct 27 ms 15880 KB Output is correct
8 Correct 41 ms 16436 KB Output is correct
9 Correct 33 ms 16424 KB Output is correct
10 Correct 28 ms 13900 KB Output is correct
11 Correct 28 ms 14000 KB Output is correct
12 Correct 27 ms 13940 KB Output is correct
13 Correct 28 ms 13920 KB Output is correct
14 Correct 28 ms 14156 KB Output is correct
15 Correct 30 ms 14460 KB Output is correct
16 Correct 33 ms 16504 KB Output is correct

Subtask #3
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 13436 KB Output is correct
2 Correct 1 ms 1820 KB Output is correct
3 Correct 24 ms 13172 KB Output is correct
4 Correct 34 ms 15136 KB Output is correct
5 Correct 37 ms 14932 KB Output is correct
6 Correct 31 ms 13548 KB Output is correct
7 Correct 28 ms 13576 KB Output is correct
8 Correct 31 ms 14124 KB Output is correct
9 Correct 31 ms 14196 KB Output is correct
10 Correct 30 ms 13940 KB Output is correct
11 Correct 30 ms 13956 KB Output is correct
12 Correct 31 ms 13888 KB Output is correct
13 Correct 30 ms 13940 KB Output is correct
14 Correct 31 ms 14192 KB Output is correct
15 Correct 32 ms 14192 KB Output is correct

Subtask #4
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 13436 KB Output is correct
2 Correct 1 ms 1820 KB Output is correct
3 Correct 24 ms 13172 KB Output is correct
4 Correct 34 ms 15136 KB Output is correct
5 Correct 37 ms 14932 KB Output is correct
6 Correct 31 ms 13548 KB Output is correct
7 Correct 28 ms 13576 KB Output is correct
8 Correct 31 ms 14124 KB Output is correct
9 Correct 31 ms 14196 KB Output is correct
10 Correct 30 ms 13940 KB Output is correct
11 Correct 30 ms 13956 KB Output is correct
12 Correct 31 ms 13888 KB Output is correct
13 Correct 30 ms 13940 KB Output is correct
14 Correct 31 ms 14192 KB Output is correct
15 Correct 32 ms 14192 KB Output is correct
16 Correct 28 ms 11792 KB Output is correct
17 Correct 27 ms 11840 KB Output is correct
18 Correct 27 ms 12044 KB Output is correct
19 Correct 25 ms 11824 KB Output is correct
20 Correct 28 ms 12628 KB Output is correct
21 Correct 27 ms 12392 KB Output is correct
22 Correct 38 ms 14424 KB Output is correct
23 Correct 26 ms 12152 KB Output is correct
24 Correct 27 ms 12144 KB Output is correct

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2064 KB Output is correct
2 Correct 1 ms 1824 KB Output is correct
3 Correct 2 ms 2080 KB Output is correct
4 Correct 2 ms 2076 KB Output is correct
5 Correct 2 ms 2080 KB Output is correct
6 Correct 2 ms 2068 KB Output is correct
7 Correct 2 ms 2072 KB Output is correct
8 Correct 2 ms 2080 KB Output is correct
9 Correct 2 ms 2076 KB Output is correct
10 Correct 2 ms 2072 KB Output is correct
11 Correct 2 ms 2068 KB Output is correct
12 Correct 2 ms 2076 KB Output is correct
13 Correct 2 ms 2072 KB Output is correct
14 Correct 2 ms 2072 KB Output is correct
15 Correct 2 ms 2084 KB Output is correct
16 Correct 2 ms 2084 KB Output is correct
17 Correct 2 ms 2112 KB Output is correct
18 Correct 2 ms 2084 KB Output is correct
19 Correct 3 ms 2080 KB Output is correct
20 Correct 2 ms 2076 KB Output is correct
21 Correct 2 ms 2084 KB Output is correct
22 Correct 2 ms 2084 KB Output is correct
23 Correct 2 ms 2076 KB Output is correct
24 Correct 2 ms 2076 KB Output is correct
25 Correct 2 ms 2084 KB Output is correct
26 Correct 2 ms 2084 KB Output is correct
27 Correct 2 ms 2076 KB Output is correct
28 Correct 2 ms 2076 KB Output is correct

Subtask #6
0 / 71.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 11984 KB Output is correct
2 Correct 27 ms 13176 KB Output is correct
3 Correct 1 ms 1808 KB Output is correct
4 Correct 26 ms 11792 KB Output is correct
5 Correct 34 ms 14676 KB Output is correct
6 Correct 34 ms 14712 KB Output is correct
7 Incorrect 29 ms 13604 KB Wrong Answer [6]
8 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 11892 KB Output is correct
2 Correct 27 ms 12916 KB Output is correct
3 Correct 1 ms 1816 KB Output is correct
4 Correct 22 ms 12104 KB Output is correct
5 Correct 32 ms 15180 KB Output is correct
6 Correct 46 ms 15192 KB Output is correct
7 Correct 27 ms 14232 KB Output is correct
8 Correct 28 ms 14120 KB Output is correct
9 Correct 34 ms 15120 KB Output is correct
10 Correct 45 ms 14912 KB Output is correct
11 Correct 31 ms 15324 KB Output is correct
12 Correct 32 ms 15152 KB Output is correct
13 Correct 32 ms 15092 KB Output is correct
14 Correct 36 ms 15192 KB Output is correct
15 Incorrect 27 ms 15188 KB Wrong Answer [6]
16 Halted 0 ms 0 KB -