Submission #765715

#	Time	Username	Problem	Language	Result	Execution time	Memory
765715		minhcool	Airline Route Map (JOI18_airline)	C++17	69 / 100	595 ms	28180 KiB

Alice

//#define local
#ifndef local
#include "Alicelib.h"
#endif
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

//#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 3e5 + 5;

const int oo = 1e18 + 7, mod = 1e9 + 7;

mt19937 rng(1);

int rnd(int l, int r){
	int temp = rng() % (r - l + 1);
	return abs(temp) + l;
}

bool ck[1505][1505];

void Alice( int N, int M, int A[], int B[]){
	int tol_nodes = N + ceil(log2(N)) * 2 + 1;
	// first node in order to know n
	// next log2(n) nodes for addition
	// next nodes for getting permutation
	if(N == 2 && !M){
		InitG(tol_nodes + 2, 0);
		return;
	}
	for(int i = 1; i <= ceil(log2(N)); i++){
		for(int j = i + 1; j <= ceil(log2(N)); j++) ck[i][j] = 1;
		for(int j = 2 * ceil(log2(N)) + 1; j <= 2 * ceil(log2(N)) + N; j++){
			int a = i - ceil(log2(N)) - 1, b = j - 2 * ceil(log2(N)) - 1;
			if(!(b & (1LL << a))){
				ck[i][j] = 1;
			//	cout << "EDGE2 " << i << " " << j << "\n";
			}
		}
	}
	for(int i = ceil(log2(N)) + 1; i <= 2 * ceil(log2(N)); i++){
		for(int j = 2 * ceil(log2(N)) + 1; j < tol_nodes; j++){
			int a = i - 1 - ceil(log2(N)), b = j - 2 * ceil(log2(N)) - 1;
			if(b & (1LL << a)){
				ck[i][j] = 1;
		//		cout << "EDGE2 " << i << " " << j << "\n";
			}
		}
	}
	int maxi = -1;
	for(int i = 2 * ceil(log2(N)); i >= ceil(log2(N)) + 1; i--){
		int deg = 0;
		for(int j = 1; j < tol_nodes; j++) deg += (ck[i][j] | ck[j][i]);
		if(deg <= maxi && i <= 2 * ceil(log2(N))){
			for(int j = 1; j <= (maxi - deg + 1); j++) ck[j][i] = 1;
			deg += (maxi - deg + 1);
		}
		maxi = max(maxi, deg);
	//	cout << maxi << '\n';
	}
	for(int i = 0; i < M; i++){
		if(A[i] > B[i]) swap(A[i], B[i]);
		ck[A[i] + 2 * (int)ceil(log2(N)) + 1][B[i] + 2 * (int)ceil(log2(N)) + 1] = 1;
	}
	vector<ii> edges;
	vector<int> degs(tol_nodes + 6);
	for(int i = 1; i < tol_nodes; i++) ck[i][tol_nodes] = 1;
	for(int i = 1; i <= 2 * ceil(log2(N)); i++) ck[i][tol_nodes + 1] = 1;
	for(int i = tol_nodes + 2; i < tol_nodes + 3; i++) ck[tol_nodes][i] = 1;
	for(int i = 1; i < tol_nodes + 3; i++){
		for(int j = i + 1; j < tol_nodes + 3; j++){
			if(ck[i][j]){
		//		cout << i << " " << j << "\n";
				edges.pb({i, j});
				degs[i]++, degs[j]++;
			}
		}
	}
//	for(int i = 1; i < tol_nodes + 5; i++) cout << "DEGS " << i << " " << degs[i] << "\n";
	
	InitG(tol_nodes + 2, edges.size());
	int pos = 0;
	for(auto it : edges){
		MakeG(pos, it.fi - 1, it.se - 1);
		pos++;
	}
}

#ifdef local
void process(){

}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	process();
}
#endif

Bob

//#define local
#ifndef local
#include "Boblib.h"
#endif
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

//#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 3e5 + 5;

const int oo = 1e18 + 7, mod = 1e9 + 7;

//mt19937 rng(1);

vector<ii> deg;

bool ckk[1505][1505];

int which[N];

bool is[N];

bool cmp(ii a, ii b){
	if(is[a.se] != is[b.se]) return is[a.se];
	else if(a.fi != b.fi) return a.fi > b.fi;
	else return a.se < b.se;
}

void Bob(int V, int U, int C[], int D[]){
	//return;
	int n;
	for(int i = 0; i <= 3000; i++){
	//	cout << i << " " << V << "\n";
		int temp = i + 2 * ceil(log2(i)) + 3;
		if(temp == V){
			n = i;
			break;
		}
	}
//	cout << n << "\n";
//	return;
	deg.resize(V);
	if(n == 1){
		InitMap(1, 0);
		return;
	}
	else if(n == 2 && !U){
		InitMap(2, 0);
		return;
	}
	else if(n == 2){
		InitMap(2, 1);
		MakeMap(0, 1);
		return;
	}
	for(int i = 0; i < V; i++) deg[i].se = i;
	for(int i = 0; i < U; i++){
		deg[C[i]].fi++;
		deg[D[i]].fi++;
		ckk[C[i]][D[i]] = ckk[D[i]][C[i]] = 1;
	//	cout << C[i] << " " << D[i] << "\n";
	}
	sort(deg.begin(), deg.end(), greater<ii>());
	int temp = deg[0].se, temp2;
	for(int i = 0; i < V; i++) if(i != temp && !ckk[i][temp]) temp2 = i;
//	cout << temp << " " << temp2 << "\n";
	vector<ii> deg2 = deg;
	deg.clear();
	for(int i = 0; i < V; i++){
		if(deg2[i].se == temp || deg2[i].se == temp2) continue;
	//	cout << deg2[i].se << " " << ckk[deg2[i].se][temp2] << "\n";
		if(ckk[deg2[i].se][temp2]) is[deg2[i].se] = 1;
		deg.pb(deg2[i]);
	}
	sort(deg.begin(), deg.end(), cmp);
	// first up: the nodes for addition (log2(n)) nodes
	// second up: the nodes from (log2(n) - 1 to 0)
	for(int i = ceil(log2(n)); i < 2 * ceil(log2(n)); i++){
		for(int j = 2 * ceil(log2(n)); j < 2 * ceil(log2(n)) + n; j++){
	//		cout << deg[i].se << " " << deg[j].se << "\n";
			if(ckk[deg[i].se][deg[j].se]){
	//			cout << "EDGE " << deg[i].se << " " << deg[j].se << "\n";
				which[deg[j].se] += (1LL << (i - (int)ceil(log2(n))));
			}
		} 
	}
	vector<ii> v;
	for(int j = 2 * ceil(log2(n)); j < 2 * ceil(log2(n)) + n; j++){
		for(int k = j + 1; k < 2 * ceil(log2(n)) + n; k++){
			//cout << deg[j].se << " " << deg[k].se << " " << which[deg[j].se] << " " << which[deg[k].se] << "\n";
			if(ckk[deg[j].se][deg[k].se]) v.pb({min(which[deg[j].se], which[deg[k].se]), max(which[deg[j].se], which[deg[k].se])});
		}
	}
	//cout << n << " " << v.size() << "\n";
	//for(int i = 0; i < n + 2 * ceil(log2(n)); i++) cout << "OK " << i << " " << which[i] << "\n";
	InitMap(n, (int)v.size());
	for(auto it : v) MakeMap(it.fi, it.se);
}

/*
int rnd(int l, int r){
	int temp = rng() % (r - l + 1);
	return abs(temp) + l;
}*/



#ifdef local
void process(){

}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t;
	cin >> t;
	while(t--) process();
}
#endif

Compilation message (stderr)

Alice.cpp:22:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   22 | const int oo = 1e18 + 7, mod = 1e9 + 7;
      |                ~~~~~^~~

Bob.cpp:22:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   22 | const int oo = 1e18 + 7, mod = 1e9 + 7;
      |                ~~~~~^~~
Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:62:7: warning: 'n' may be used uninitialized in this function [-Wmaybe-uninitialized]
   62 |  else if(n == 2){
      |       ^~

• Subtask 1: 22 / 22
• Subtask 2: 15 / 15
• Subtask 3: 32 / 63