Submission #915657

#TimeUsernameProblemLanguageResultExecution timeMemory
915657winter0101Airline Route Map (JOI18_airline)C++14
100 / 100
550 ms43780 KiB
#include<bits/stdc++.h> #include "Alicelib.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) void Alice( int N, int M, int A[], int B[] ){ int n=N+12; vector<pii>t; for1(i,0,M-1){ t.pb({A[i],B[i]}); } for1(i,0,N+10){ if (i==N)continue; t.pb({N,i}); } for1(i,N+1,N+10)t.pb({N+11,i}); for1(i,N+2,N+10){ t.pb({i,i-1}); } for1(i,1,N){ for1(j,0,9){ if (i>>j&1){ t.pb({i-1,j+1+N}); } } } InitG(n,sz(t)); for1(i,0,sz(t)-1){ auto u=t[i]; MakeG(i,u.fi,u.se); } }
#include<bits/stdc++.h> #include "Boblib.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=2e3+9; int deg[maxn]; vector<int>a[maxn]; bool b[maxn][maxn]; bool isbit[maxn]; bool vis[maxn]; vector<int>ord; void dfs(int u){ vis[u]=1; ord.pb(u); for (auto v:a[u]){ if (isbit[v]&&!vis[v]){ dfs(v); } } } int encode[maxn]; void Bob( int V, int U, int C[], int D[] ){ int n=V-12; for1(i,0,U-1){ deg[C[i]]++; deg[D[i]]++; a[C[i]].pb(D[i]); a[D[i]].pb(C[i]); b[C[i]][D[i]]=b[D[i]][C[i]]=1; } int nw=0; for1(i,0,V-1){ if (deg[i]>deg[nw])nw=i; } int sec=0; for1(i,0,V-1){ if (i==nw)continue; if (!b[nw][i]){ sec=i; } } vector<int>bit; for (auto v:a[sec]){ isbit[v]=1; bit.pb(v); } vector<int>bit09; for (auto v:bit){ int cnt=0; for (auto u:a[v]){ cnt+=isbit[u]; } if (cnt==1)bit09.pb(v); } int u=bit09[0],v=bit09[1]; if (sz(a[u])>sz(a[v]))bit09.pop_back(); int bit0=bit09.back(); dfs(bit0); for1(i,0,sz(ord)-1){ for (auto v:a[ord[i]]){ if (v==nw||v==sec)continue; encode[v]+=(1<<i); } } vector<pii>t; for1(i,0,U-1){ if (C[i]==nw||C[i]==sec||isbit[C[i]]||D[i]==nw||D[i]==sec||isbit[D[i]])continue; t.pb({encode[C[i]]-1,encode[D[i]]-1}); } InitMap(n,sz(t)); for (auto v:t)MakeMap(v.fi,v.se); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...