Submission #912308

#TimeUsernameProblemLanguageResultExecution timeMemory
912308winter0101Stray Cat (JOI20_stray)C++14
100 / 100
47 ms17008 KiB
#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 (stderr)

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 | }
      | ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...