Submission #995029

#TimeUsernameProblemLanguageResultExecution timeMemory
995029maomao90Airline Route Map (JOI18_airline)C++17
37 / 100
355 ms46356 KiB
// Hallelujah, praise the one who set me free // Hallelujah, death has lost its grip on me // You have broken every chain, There's salvation in your name // Jesus Christ, my living hope #include <bits/stdc++.h> #include "Alicelib.h" using namespace std; #define REP(i, s, e) for (int i = (s); i < (e); i++) #define RREP(i, s, e) for (int i = (s); i >= (e); i--) template <class T> inline bool mnto(T& a, T b) {return b < a ? a = b, 1 : 0;} template <class T> inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;} typedef unsigned long long ull; typedef long long ll; typedef long double ld; #define FI first #define SE second typedef pair<int, int> ii; typedef pair<ll, ll> pll; typedef tuple<int, int, int> iii; #define ALL(_a) _a.begin(), _a.end() #define SZ(_a) (int) _a.size() #define pb push_back typedef vector<int> vi; typedef vector<ll> vll; typedef vector<ii> vii; typedef vector<iii> viii; #ifndef DEBUG #define cerr if (0) cerr #endif const int INF = 1000000005; const ll LINF = 1000000000000000005ll; const int MAXN = 1100; namespace { int n, m; bool g[MAXN][MAXN], h[MAXN][MAXN]; inline void add(int u, int v) { h[u][v] = h[v][u] = 1; } inline void answer() { vii eg; REP (i, 0, m) { REP (j, i + 1, m) { if (h[i][j]) { eg.pb({i, j}); } } } InitG(m, SZ(eg)); REP (i, 0, SZ(eg)) { MakeG(i, eg[i].FI, eg[i].SE); } } } void Alice(int N, int E, int A[], int B[]) { n = N; REP (i, 0, E) { g[A[i]][B[i]] = g[B[i]][A[i]] = 1; } REP (i, 0, n) { REP (j, 0, n) { h[i][j] = g[i][j]; } } if (n <= 2) { m = n; answer(); return; } int lg = 32 - __builtin_clz(n - 1); m = n + min(lg + 3, 12); REP (l, 0, lg) { REP (i, 0, n) { if (i >> l & 1) { add(n + l, i); } } if (l) { add(n + l, n + l - 1); } } if (lg == 10) { REP (i, n, n + lg + 1) { add(n + lg, i); } REP (i, 0, n + lg) { add(n + lg + 1, i); } } else { add(n + lg, n + lg - 1); REP (i, n, n + lg + 1) { add(n + lg + 1, i); } REP (i, 0, n + lg + 1) { add(n + lg + 2, i); } } answer(); }
// Hallelujah, praise the one who set me free // Hallelujah, death has lost its grip on me // You have broken every chain, There's salvation in your name // Jesus Christ, my living hope #include <bits/stdc++.h> #include "Boblib.h" using namespace std; #define REP(i, s, e) for (int i = (s); i < (e); i++) #define RREP(i, s, e) for (int i = (s); i >= (e); i--) template <class T> inline bool mnto(T& a, T b) {return b < a ? a = b, 1 : 0;} template <class T> inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;} typedef unsigned long long ull; typedef long long ll; typedef long double ld; #define FI first #define SE second typedef pair<int, int> ii; typedef pair<ll, ll> pll; typedef tuple<int, int, int> iii; #define ALL(_a) _a.begin(), _a.end() #define SZ(_a) (int) _a.size() #define pb push_back typedef vector<int> vi; typedef vector<ll> vll; typedef vector<ii> vii; typedef vector<iii> viii; #ifndef DEBUG #define cerr if (0) cerr #endif const int INF = 1000000005; const ll LINF = 1000000000000000005ll; const int MAXN = 1100; namespace { int n, m; bool g[MAXN][MAXN], h[MAXN][MAXN]; inline void add(int u, int v) { h[u][v] = h[v][u] = 1; } int deg[MAXN]; bool isb[MAXN], vis[MAXN]; int id[MAXN]; inline bool rmv(int u, int v) { if (!g[u][v]) { return 0; } g[u][v] = g[v][u] = 0; deg[u]--; deg[v]--; return 1; } inline void answer() { vii eg; REP (i, 0, m) { REP (j, i + 1, m) { if (h[i][j]) { eg.pb({i, j}); } } } InitMap(m, SZ(eg)); REP (i, 0, SZ(eg)) { MakeMap(eg[i].FI, eg[i].SE); } } } void Bob(int V, int U, int C[], int D[]) { REP (i, 0, U) { g[C[i]][D[i]] = g[D[i]][C[i]] = 1; } n = V; if (n <= 2) { m = n; REP (i, 0, n) { REP (j, 0, n) { h[i][j] = g[i][j]; } } answer(); return; } REP (x, 1, MAXN) { int lg = 32 - __builtin_clz(x - 1); if (x + min(12, lg + 3) == n) { m = x; break; } } assert(m); int lg = 32 - __builtin_clz(m - 1); ii mx = {0, 0}; REP (i, 0, n) { REP (j, 0, n) { deg[i] += g[i][j]; } mxto(mx, {deg[i], i}); } assert(mx.FI == n - 2); int r = -1; REP (i, 0, n) { if (i == mx.SE) { continue; } if (!rmv(mx.SE, i)) { assert(r == -1); r = i; } } assert(deg[r] == lg + 1); REP (i, 0, n) { isb[i] = rmv(r, i); } vi bits; if (lg == 10) { ii mn = {INF, INF}; REP (i, 0, n) { if (!isb[i]) { continue; } int bdeg = 0; REP (j, 0, n) { bdeg += isb[j] && g[i][j]; } if (bdeg == 1) { mnto(mn, {deg[i], i}); } } assert(mn.SE != INF); bits.pb(mn.SE); vis[mn.SE] = 1; } else { int e = -1; REP (i, 0, n) { if (isb[i] && deg[i] == 1) { REP (j, 0, n) { if (isb[j] && g[i][j]) { e = i; break; } } if (e != -1) { break; } } } assert(e != -1); assert(deg[e] == 1); REP (i, 0, n) { if (rmv(e, i)) { bits.pb(i); vis[i] = 1; } } } while (SZ(bits) < lg) { REP (i, 0, n) { if (vis[i] || !isb[i]) { continue; } if (rmv(bits.back(), i)) { vis[i] = 1; bits.pb(i); break; } } } reverse(ALL(bits)); REP (l, 0, lg) { REP (i, 0, n) { id[i] |= rmv(bits[l], i) << l; } } REP (i, 0, n) { REP (j, 0, n) { if (g[i][j]) { assert(id[i] < m && id[j] < m); add(id[i], id[j]); } } } answer(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...