Submission #1009895

#TimeUsernameProblemLanguageResultExecution timeMemory
1009895pccGame (APIO22_game)C++17
60 / 100
1224 ms39140 KiB
#include "game.h" #include <bits/stdc++.h> using namespace std; #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,popcnt,sse4") const int mxk = 1010; const int mxn = 3e4+10; bool flag = false; char cnt[mxk*mxn]; int N,K; void add(int k){ assert(k<mxn*mxk); cnt[k]++; if(cnt[k]>=2)flag = true; return; } const int LEN = 1e5+10; int head[LEN],to[LEN],nid[LEN],p1; int rhead[LEN],rto[LEN],rnid[LEN],p2; void add_edge(short a,short b){ assert(p1<LEN); //cerr<<a<<','<<b<<':'<<p1<<endl; p1++; nid[p1] = head[a]; to[p1] = b; head[a] = p1; } void radd_edge(short a,short b){ assert(p2<LEN); p2++; rnid[p2] = rhead[a]; rto[p2] = b; rhead[a] = p2; return; } struct DS{ bitset<mxn> vis,rvis; short id; DS(short ii = 0):id(ii){vis.reset();rvis.reset();} queue<short> q; void BFS(short now){ if(vis[now])return; q.push(now); vis[now] = true;add(N*id+now); while(!q.empty()){ auto now = q.front(); q.pop(); for(int eid = head[now];eid;eid = nid[eid]){ int nxt = to[eid]; if(vis[nxt])continue; vis[nxt] = true;add(N*id+nxt); q.push(nxt); } } return; } void RBFS(short now){ if(rvis[now])return; q.push(now); rvis[now] = true;add(N*id+now); while(!q.empty()){ auto now = q.front(); q.pop(); for(int eid = rhead[now];eid;eid = rnid[eid]){ int nxt = rto[eid]; if(rvis[nxt])continue; rvis[nxt] = true;add(N*id+nxt); q.push(nxt); } } return; } void add_edge(short a,short b){ if(vis[a])BFS(b); if(rvis[b])RBFS(a); return; } }; DS arr[mxk]; void init(int n, int k) { N = n,K = k; for(int i = 0;i<k;i++){ arr[i].id = i; arr[i].vis[i] = arr[i].rvis[i] = 1; } for(short i = 0;i<=k-2;i++){ add_edge(i,i+1); radd_edge(i+1,i); for(short j = 0;j<k;j++){ arr[j].add_edge(i,i+1); } } flag = false; /* cerr<<"INIT DONE!"<<endl; for(int i = 0;i<K;i++){ for(int j = 0;j<N;j++)cerr<<arr[i].vis[j];cerr<<endl; for(int j = 0;j<N;j++)cerr<<arr[i].rvis[j];cerr<<endl; cerr<<endl; } */ return; } int add_teleporter(int u, int v) { if(u == v){ return (u<K); } add_edge(u,v); radd_edge(v,u); for(short i = 0;i<K;i++){ arr[i].add_edge(u,v); } return flag; }
#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...