| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1214681 | mychecksedad | Airline Route Map (JOI18_airline) | C++20 | 0 ms | 0 KiB |
#include "Alicelib.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30;
void Alice( int n, int m, int A[], int B[] ){
vector<vector<bool>> E(n, vector<bool>(n));
for(int i = 0; i <m; ++i) if(A[i]> B[i]) swap(A[i], B[i]);
for(int i = 0; i <m; ++i) E[A[i]][B[i]] = 1;
vector<pii> P;
for(int i = 0; i < n; ++i){
for(int j = i + 1; j < n; ++j){
if(E[i][j]){
P.pb({i, j});
}
}
}
vi ID;
for(int i = 0; i < 1024; ++i){
if(__builtin_popcount(i) >= 2) ID.pb(i);
}
stable_sort(all(ID), [&](const int &x, const int &y){
bool a = x % 2;
bool b = y % 2;
if(a == b) return x < y;
if(a) return true;
return false;
});
for(int i = 0; i < n; ++i){
for(int j = 0; j < 10; ++j){
if((1<<j)&ID[i]){
deg[j]++;
P.pb({i, n + j});
}
}
}
int t = n + 11;
int s = n + 10;
P.pb({s, t});
for(int i = n; i < n + 10; ++i){
P.pb({s, i});
}
for(int i = n + 5; i < n + 10; ++i){
for(int j = i + 1; j < n + 10; ++j) P.pb({i, j});
}
for(int i = n + 4; i >= n; --i){
for(int j = n+9, ptr = 0; ptr < (n+4-i); ++ptr, --j) P.pb({i, j});
}
int cnt = 0;
InitG(n + 12, int(P.size()));
for(auto [x, y]: P){
// cerr << x << ' ' << y << '\n';
MakeG(cnt++, x, y);
}
}
#include "Boblib.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30;
void assertt(bool b){
if(!b){
vi v;
for(int i = 1; i <= MOD; ++i){
v.pb(i);
}
}
}
void Bob( int nn, int mm, int C[], int D[] ){
int n = nn - 12;
vi deg(nn);
vector<vector<bool>> E(nn, vector<bool>(nn));
for(int i = 0; i < mm; ++i){
deg[C[i]]++;
deg[D[i]]++;
E[C[i]][D[i]] = E[D[i]][C[i]] = 1;
}
int t = -1;
for(int i = 0; i < nn; ++i){
if(deg[i] == 1){
if(t == -1) t = i;
else assertt(false);
}
}
// return;
int s = -1;
for(int i = 0; i < nn; ++i){
if(E[t][i]){
if(s != -1) assertt(false);
s = i;
}
}
vi A;
for(int i = 0; i < nn; ++i){
if(i == s || i == t) continue;
if(E[i][s]) A.pb(i);
}
vi degg(nn);
for(int j = 0; j < 10; ++j){
for(int i = 0; i < 10; ++i) degg[A[j]] += E[A[j]][A[i]];
}
sort(all(A), [&](const int &x, const int &y){
return degg[x] < degg[y];
});
// 5, 4, 3, 2, 1, 6, 7, 8, 9, 10
// 5, 4, 3, 2, 6, 1, 7, 8, 9, 10
swap(A[1], A[3]);
// for(int i = 1; i <= 10; ++i){
// cerr << deg[A[i-1]] << ' ';
// }
// 5, 2, 3, 4, 1, 6, 7, 8, 9, 10
// 5, 2, 3, 4, 6, 1, 7, 8, 9, 10
if(deg[A[4]] > deg[A[5]]){
swap(A[0], A[4]);
}else{
swap(A[4], A[5]);
swap(A[0], A[4]);
}
vi node(n, -1);
vi ID;
for(int i = 0; i < 1024; ++i){
if(__builtin_popcount(i) >= 2) ID.pb(i);
}
stable_sort(all(ID), [&](const int &x, const int &y){
bool a = x % 2;
bool b = y % 2;
if(a == b) return x < y;
if(a) return true;
return false;
});
vi pos(1024, -1);
for(int i = 0; i < ID.size(); ++i) pos[ID[i]] = i;
for(int i = 0; i < nn; ++i){
if(i == s || i == t) continue;
bool in = false;
for(int x: A) in = in | (x == i);
if(in) continue;
int sum = 0;
for(int j = 0; j < 10; ++j) sum += (1<<(j)) * E[i][A[j]];
node[pos[sum]] = i;
cerr << pos[sum] << ' ' << sum << '\n';
}
for(int i = 0; i < n; ++i){
assertt(node[i] != -1);
}
vector<pii> P;
for(int i = 0; i < n; ++i){
for(int j = i + 1; j < n; ++j){
int v = node[i], u = node[j];
if(E[u][v]) P.pb({i, j});
}
}
InitMap(n, int(P.size()));
for(auto [x, y]: P) MakeMap(x, y);
}