| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 565924 | Spade1 | Airline Route Map (JOI18_airline) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#include "Alicelib.h"
#define pii pair<int, int>
#define pll pair<long long, long long>
#define ll long long
#define ld long double
#define st first
#define nd second
#define pb push_back
#define INF INT_MAX
using namespace std;
int cnt = 0;
void Alice(int N, int M, int A[], int B[]) {
int binarycount = 0;
for (int i = 1; i <= N; ++i) {
binarycount += __builtin_popcount(i);
}
initG(N+12, N+M+binarycount+10);
for (int i = 0; i < M; ++i) {
MakeG(cnt++, A[i], B[i]);
}
for (int i = 0; i < N; ++i) {
MakeG(cnt++, N, i);
}
MakeG(N+1, N);
for (int i = N+2; i < N+11; ++i) {
MakeG(cnt++, i, i+1);
}
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= 10; ++j) {
if (i & (1<<j)) MakeG(cnt++, i, N+1+j);
}
}
}
#include<bits/stdc++.h>
#include "Boblib.h"
#define pii pair<int, int>
#define pll pair<long long, long long>
#define ll long long
#define ld long double
#define st first
#define nd second
#define pb push_back
#define INF INT_MAX
using namespace std;
vector<int> adj;
int unmap[1050];
int bit[11];
bool part[1050];
int deg[1050];
set<int> sbit;
void findbit(int i) {
if (i == 10) return;
for (auto j : adj[bit[i]]) {
if (!sbit.count(j) && !part[j]) {
bit[i+1] = j;
break;
}
}
findbit(i+1);
}
void Bob(int V, int U, int C[], int D[]) {
int binarycount = 0;
memset(upmap, -1, sizeof(unmap));
int N = V-12, M = U-V+2-binarycount;
for (int i = 1; i <= (V-12); ++i) {
binarycount += __builtin_popcount(i);
}
InitMap(N, M);
for (int i = 0; i < V; ++i) {
adj[C[i]].pb(D[i]);
adj[D[i]].pb(C[i]);
deg[C[i]]++, deg[D[i]]++;
}
int key, ckey;
for (int i = 0; i < V; ++i) {
if (deg[i] == 1 && deg[adj[i][0]] == N+1) {
key = adj[i][0];
ckey = i;
}
}
for (int i = 0; i < V; ++i) {
if (i == key || i == ckey) continue;
for (auto j : adj[i]) {
if (j == key) part[i] = 1;;
}
}
vector<int> edge;
for (int i = 0; i < V; ++i) {
if (!part[i]) {
int cnt = 0;
for (auto j : adj[i]) {
if (part[i]) continue;
cnt++;
}
if (cnt == 1) ed.pb(i);
}
}
if (adj[edge[0]].size() > adj[edge[1]].size()) bit[1] = edge[0];
else bit[1] = edge[1];
sbit.insert(bit[1]);
findbit(1);
for (int i = 0; i < V; ++i) {
if (i == key || i == ckey) continue;
if (sbit.count(i)) continue;
for (int j = 1; j <= 10; ++j) {
if (i & (1<<j)) unmap[i] += (1<<j);
}
}
for (int i = 0; i < U; ++i) {
if (unmap[C[i]] == -1) continue;
if (unmap[D[i]] == -1) continue;
MakeMap(unmap[D[i]], unmap[C[i]]);
}
}