Submission #995023

#TimeUsernameProblemLanguageResultExecution timeMemory
995023maomao90Airline Route Map (JOI18_airline)C++17
54 / 100
479 ms40796 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; if (n == 1) { InitG(1, 0); return; } int lg = 32 - __builtin_clz(n - 1); m = n + lg + 3; 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]; } } REP (l, 0, lg) { REP (i, 0, n) { if (i >> l & 1) { add(n + l, i); } } if (l) { add(n + l, n + l - 1); } } 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[]) { n = V; if (n == 1) { InitMap(1, 0); return; } REP (x, 1, MAXN) { int lg = 32 - __builtin_clz(x - 1); if (x + lg + 3 == n) { m = x; break; } } assert(m); int lg = abs(n - m) - 3; REP (i, 0, U) { g[C[i]][D[i]] = g[D[i]][C[i]] = 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); } 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); vi bits; 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...