Submission #883186

#TimeUsernameProblemLanguageResultExecution timeMemory
883186NK_Airline Route Map (JOI18_airline)C++17
100 / 100
567 ms39908 KiB
// Success consists of going from failure to failure without loss of enthusiasm #include <bits/stdc++.h> #include "Alicelib.h" using namespace std; #define nl '\n' #define pb push_back #define sz(x) int(x.size()) #define f first #define s second #define mp make_pair using ll = long long; template<class T> using V = vector<T>; using vi = V<int>; using pi = pair<int, int>; using vpi = V<pi>; const int EX = 12; const int B = 10; void Alice(int N, int M, int C[], int D[]){ int EXT = N + EX - 1; int PATH = N + EX - 2; vpi E; for(int i = 0; i < M; i++) { E.pb(mp(C[i], D[i])); } int cur = 1; for(int i = 0; i < N; i++) { while(__builtin_popcount(cur) == 1) cur++; for(int b = 0; b < B; b++) if ((cur >> b) & 1) { E.pb(mp(N + b, i)); } ++cur; } // cout << "MX: " << cur << endl; // cout << "PATH: " << PATH << endl; for(int i = 0; i < B; i++) { if (i) E.pb(mp(N + i - 1, N + i)); else E.pb(mp(PATH, N + i)); } for(int i = 0; i < B; i++) { E.pb(mp(N + i, EXT)); } InitG(N + EX, sz(E)); for(int i = 0; i < sz(E); i++) { MakeG(i, E[i].f, E[i].s); } }
// Success consists of going from failure to failure without loss of enthusiasm #include <bits/stdc++.h> #include "Boblib.h" using namespace std; #define nl '\n' #define pb push_back #define sz(x) int(x.size()) #define f first #define s second #define mp make_pair using ll = long long; template<class T> using V = vector<T>; using vi = V<int>; using pi = pair<int, int>; using vpi = V<pi>; const int EX = 12; const int B = 10; void Bob(int N, int M, int C[], int D[]){ int cur = 1; map<int, int> conv; vi F(B); for(int i = 0; i < (N - EX); i++) { while(__builtin_popcount(cur) == 1) cur++; for(int b = 0; b < B; b++) if ((cur >> b) & 1) F[b]++; conv[cur++] = i; } V<vi> adj(N); for(int i = 0; i < M; i++) { adj[C[i]].pb(D[i]); adj[D[i]].pb(C[i]); } // cout << B + N - EX << endl; vi BITS(B); vi X(N); int PATH = -1; for(int i = 0; i < N; i++) if (sz(adj[i]) == 1) { PATH = i; } // cout << PATH << endl; int times = 0; for(int i = 0; i < N; i++) if (sz(adj[i]) == B) { int EXT = i; set<int> left; for(auto &x : adj[EXT]) left.insert(x); vi path; int u = PATH; for(int x = 0; x < B; x++) { bool found = 0; for(auto& v : adj[u]) { if (left.count(v)) { left.erase(v); u = v; found = 1; break; } } if (found) { path.pb(u); } else { path = {}; break; } } if (sz(path) == 0 || sz(left)) continue; assert(sz(path) == B); set<int> S(begin(path), end(path)); S.insert(PATH); S.insert(EXT); // set of special nodes vi FP; for(auto& x : path) { int amt = 0; for(auto& y : adj[x]) if (!S.count(y)) amt++; FP.pb(amt); } if (F != FP) continue; X[PATH] = X[EXT] = -1; // cout << "PATH: "; for(int x = 0; x < B; x++) { // cout << path[x] << " "; X[path[x]] = -1; BITS[x] = path[x]; } // cout << endl; ++times; } // cout << times << endl; assert(times == 1); for(int i = 0; i < B; i++) { for(auto& x : adj[BITS[i]]) { if (X[x] == -1) continue; X[x] ^= (1 << i); } } vpi E; for(int u = 0; u < N; u++) { int U = X[u]; if (U == -1) continue; for(auto& v : adj[u]) { int V = X[v]; if (V == -1) continue; if (U < V) { // cout << U << " " << V << endl; // cout << conv[U] << " " << conv[V] << endl; E.pb(mp(conv[U], conv[V])); } } } // cout << sz(E) << endl; InitMap(N - EX, sz(E)); for(int i = 0; i < sz(E); i++) MakeMap(E[i].f, E[i].s); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...