Submission #700187

#TimeUsernameProblemLanguageResultExecution timeMemory
700187uroskAirline Route Map (JOI18_airline)C++14
100 / 100
776 ms58288 KiB
#include "Alicelib.h" #define here cerr<<"===========================================\n" #define dbg(x) cerr<<#x<<": "<<x<<endl; #include "bits/stdc++.h" //#include <ext/pb_ds/tree_policy.hpp> //#include <ext/pb_ds/assoc_container.hpp> #define ld double #define ll int #define llinf 100000000000000000LL // 10^17 #define pb push_back #define popb pop_back #define fi first #define sc second #define endl '\n' #define pll pair<ll,ll> #define pld pair<ld,ld> #define sz(a) (ll)(a.size()) #define all(a) a.begin(),a.end() #define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;} #define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;} #define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0); using namespace std; #define maxn 2020 void Alice(ll N,ll M,ll A[],ll B[] ){ ll n = N,m = M; ll d = 12; ll v = n+d,u = m; vector<pll> a; vector<ll> want(maxn,0); vector<ll> deg(maxn,0); vector<vector<bool> > ima(maxn,vector<bool>(maxn,0)); for(ll i = 0;i<m;i++) a.pb({A[i],B[i]}); for(ll i = 0;i<v-2;i++) a.pb({i,v-1}); for(ll i = n;i<v-2;i++) a.pb({i,v-2}); set<pll> s; for(ll i = n;i<v-2;i++) want[i] = i-n; for(ll i = 0;i<v;i++) ima[i][i] = 1; for(ll i = n;i<v-3;i++) a.pb({i,i+1}); //ceri(deg,n,v-3); for(ll i = 0;i<n;i++){ for(ll j = 0;j<d-2;j++){ if((1<<j)&i) a.pb({i,n+j}); } } u = sz(a); InitG(v,u); //dbg(sz(a)); //for(pll p : a) cerr<<p.fi<< " "<<p.sc<<endl; for(ll i = 0;i<v;i++) deg[i] = 0; for(ll i = 0;i<u;i++) deg[a[i].fi]++,deg[a[i].sc]++; //ceri(deg,0,v-1); for(ll i = 0;i<u;i++) MakeG(i,a[i].fi,a[i].sc); } /** 4 3 0 1 0 2 0 3 5 7 0 1 0 2 1 3 1 4 3 4 2 3 2 4 11 10 0 1 2 1 3 0 4 2 5 3 6 1 7 4 8 4 9 0 10 1 **/
#include "Boblib.h" #define here cerr<<"===========================================\n" #define dbg(x) cerr<<#x<<": "<<x<<endl; #include "bits/stdc++.h" //#include <ext/pb_ds/tree_policy.hpp> //#include <ext/pb_ds/assoc_container.hpp> #define ld double #define ll int #define llinf 100000000000000000LL // 10^17 #define pb push_back #define popb pop_back #define fi first #define sc second #define endl '\n' #define pll pair<ll,ll> #define pld pair<ld,ld> #define sz(a) (ll)(a.size()) #define all(a) a.begin(),a.end() #define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;} #define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;} #define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0); using namespace std; #define maxn 2020 void Bob(ll V,ll U,ll C[],ll D[]){ ll n = V,m = U; vector<ll> ans(maxn,0); vector<ll> deg(maxn,0); vector<ll> sdeg(maxn,0); vector<pll> e(maxn*maxn); vector<bool> spec(maxn,0); vector<vector<ll> > g(maxn); vector<vector<bool> > ok(maxn,vector<bool>(maxn,0)); for(ll i = 0;i<m;i++) e[i] = {C[i],D[i]}; for(ll i = 0;i<m;i++){ ll x = e[i].fi,y = e[i].sc; deg[x]++; deg[y]++; ok[x][y] = ok[y][x] = 1; g[x].pb(y); g[y].pb(x); } for(ll i = 0;i<n;i++) ok[i][i] = 1; ll u = 0; for(ll i = 0;i<n;i++) if(deg[i]>deg[u]) u = i; ll v = -1; for(ll i = 0;i<n;i++) if(!ok[u][i]){ if(v==-1) v = i; else if(deg[i]>deg[v]) v = i; } vector<ll> w; for(ll x : g[v]){ w.pb(x); spec[x] = 1; } for(ll x : w){ for(ll y : g[x]){ if(spec[y]) sdeg[x]++; } } ll poc = w[0]; for(ll x : w) if(sdeg[x]<sdeg[poc]||(sdeg[x]==sdeg[poc]&&deg[x]>deg[poc])) poc = x; vector<ll> W; vector<bool> vis(maxn,0); function<void(ll)> dfs = [&](ll u){ vis[u] = 1; W.pb(u); for(ll s : g[u]){ if(spec[s]&&!vis[s]) dfs(s); } }; dfs(poc); //dbg(poc); //dbg(deg[poc]); w.clear(); for(ll x : W) w.pb(x); spec[u] = spec[v] = 1; for(ll cnt = 0;cnt<10;cnt++){ ll x = w[cnt]; for(ll y : g[x]){ if(!spec[y]){ ans[y]+=(1<<cnt); } } } ll gr = 0; for(ll i = 0;i<m;i++){ ll x = e[i].fi,y = e[i].sc; if(spec[x]||spec[y]) continue; gr++; } InitMap(n-12,gr); for(ll i = 0;i<m;i++){ ll x = e[i].fi,y = e[i].sc; if(spec[x]||spec[y]) continue; x = ans[x],y = ans[y]; MakeMap(x,y); } } /** 4 3 0 1 0 2 0 3 **/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...