Submission #915661

#TimeUsernameProblemLanguageResultExecution timeMemory
915661winter0101Airline Route Map (JOI18_airline)C++14
100 / 100
590 ms43804 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[] ){ 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+12,sz(t)); for1(i,0,sz(t)-1)MakeG(i,t[i].fi,t[i].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],encode[maxn]; vector<int>a[maxn]; bool b[maxn][maxn],isbit[maxn],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); } void Bob( int V, int U, int C[], int D[] ){ 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(V-12,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...