| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 45140 | reality | Airline Route Map (JOI18_airline) | C++17 | 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 "Alicelib.h"
#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
const int NN = (int)(1e6) + 5;
int deg[NN];
void Alice( int N, int M, int A[], int B[] ){
vector < pii > edges;
for (int i = 0;i < N;++i)
edges.pb(mp(N,i));
for (int i = 0;i < N;++i)
for (int j = 0;j < 10;++j)
if ((i >> j) & 1)
edges.pb(mp(i,N + 1 + j));
for (int i = 0;i + 1 < 10;++i)
edges.pb(mp(i + N + 1,i + N + 2));
for (int i = 0;i < M;++i)
edges.pb(mp(A[i],B[i]));
for (int i = 0;i < N + 11;++i)
if (i != N)
edges.pb(mp(N + 11,i));
for (auto it : edges)
++deg[it.fi],++deg[it.se];
//dbg(deg[N]);
//dbg(deg[511]);
int mx = *max_element(deg,deg + N + 12);
InitG(N + 12,edges.size());
for (int i = 0;i < (edges.size());++i)
MakeG(i,edges[i].fi,edges[i].se);
}
#include "Boblib.h"
#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
const int NN = (int)(1e6) + 5;
vi < int > g[NN];
int G[2048][2048];
int p[NN];
void Bob( int V, int U, int C[], int D[] ){
int n = V - 12;
for (int i = 0;i < U;++i)
g[C[i]].pb(D[i]),g[D[i]].pb(C[i]),G[D[i]][C[i]] = G[C[i]][D[i]] = 1;
int aux = -1;
int shit = 0;
vi ps;
for (int i = 0;i < V;++i)
if (g[i].size() == V - 2)
ps.pb(i);
int sep = -1;
for (auto pp : ps) {
int lc = -1;
for (int i = 0;i < V;++i)
if (!G[pp][i] && i != aux && g[i].size() == n)
lc = i;
if (lc != -1) {
sep = lc;
aux = pp;
break;
}
}
int pw2 = -1;
for (int i = 0;i < V;++i)
if (i != sep && i != aux && !G[sep][i] && (pw2 == -1 || g[pw2].size() > g[i].size()))
pw2 = i;
vi p2;
p2.pb(pw2);
set < int > was;
was.insert(pw2);
was.insert(aux);
was.insert(sep);
for (int t = 0;t < 9;++t) {
for (auto it : g[p2.back()])
if (!was.count(it) && !G[sep][it]) {
p2.pb(it);
was.insert(it);
break;
}
}
reverse(all(p2));
for (int t = 0;t < 10;++t) {
for (auto it : g[p2[t]])
if (G[sep][it])
p[it] += (1 << t);
}
vector < pii > edges;
for (auto u : g[sep])
for (auto v : g[u])
if (G[sep][v] && u < v)
edges.pb(mp(p[u],p[v]));
InitMap(n,edges.size());
for (auto it : edges)
MakeMap(it.fi,it.se);
}