Submission #700172

#TimeUsernameProblemLanguageResultExecution timeMemory
700172uroskAirline Route Map (JOI18_airline)C++14
0 / 100
706 ms72464 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<n;i++) a.pb({i,v-1}); for(ll i = 0;i<n;i++) a.pb({i,v-2}); for(ll i = n;i<=n+4;i++) a.pb({i,v-2}); for(ll i = n+5;i<=n+8;i++) a.pb({i,v-1}); a.pb({v-1,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 = v-3;i>n;i--){ if(want[i]){ a.pb({i,n}); deg[i]++; deg[n]++; want[i]--; } ll j = i-1; while(want[i]&&j>=n){ if(want[j]&&!ima[i][j]){ ima[i][j] = ima[j][i] = 1; a.pb({i,j}); want[j]--; want[i]--; deg[i]++; deg[j]++; } j--; } } 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); 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]++; 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 **/
#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<pll> e(maxn*maxn); vector<bool> spec(maxn,0); vector<vector<ll> > g(maxn); vector<bool> ok2(maxn,0); 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); } ll N = n-12; for(ll i = 0;i<n;i++) ok[i][i] = 1; ll u = 0,v = -1; for(ll i = 0;i<n;i++){ if(deg[i]==N+5) u = i; } for(ll x : g[u]){ if(v==-1&&deg[x]==N+5) v = x; else{ if(deg[x]>deg[v]&&deg[v]==N+5) v = x; } } lol:; vector<ll> w; for(ll i = 0;i<n;i++){ if(ok[v][i]&&ok[u][i]) continue; if(i==u||i==v) continue; w.pb(i); spec[i] = 1; } spec[u] = spec[v] = 1; for(ll x : w){ ll cnt = -1; for(ll y : w){ if(ok[x][y]){ cnt++; } } if(cnt==5){ if(ok[x][u]) cnt = 0; } 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 5 7 0 1 0 2 1 3 1 4 3 4 2 3 2 4 **/

Compilation message (stderr)

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:56:5: warning: label 'lol' defined but not used [-Wunused-label]
   56 |     lol:;
      |     ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...