Submission #604823

#	Time	Username	Problem	Language	Result	Execution time	Memory
604823		alireza_kaviani	Airline Route Map (JOI18_airline)	C++17	37 / 100	783 ms	27280 KiB

Alice

#include "Alicelib.h"
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

#define X		first
#define Y 		second
#define SZ(x)	int((x).size())

const int MAXN = 1510;
const int LOG = 10;

void Alice(int N, int M, int A[], int B[]){
	vector<pii> E;
	for(int i = 0 ; i < M ; i++){
		E.push_back({A[i] , B[i]});
	}
	for(int i = N ; i <= N + 100 ; i++){
		for(int j = 0 ; j < i ; j++){
			E.push_back({j , i});
		}
	}
	for(int i = N + 101 ; i <= N + 200 ; i++){
		for(int j = N ; j <= N + 100 ; j++){
			if(i % 2 == j % 2){
				E.push_back({j , i});
			}
		}
	}
	for(int i = 0 ; i < LOG ; i++){
		for(int j = 0 ; j < N ; j++){
			if(j & (1 << i)){
				E.push_back({j , N + 201 + i});
			}
		}
		for(int j = N ; j < N + i ; j++){
			E.push_back({j , N + 201 + i});
		}
	}
	InitG(N + 201 + LOG , SZ(E));
	for(int i = 0 ; i < SZ(E) ; i++){
		MakeG(i , E[i].X , E[i].Y);
	}
}

Bob

#include "Boblib.h"
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

#define X		first
#define Y 		second
#define SZ(x)	int((x).size())

const int MAXN = 1510;
const int LOG = 10;

int deg[MAXN] , deg2[MAXN] , ind[MAXN] , type[MAXN];

void Bob(int N, int M, int A[], int B[]){
	for(int i = 0 ; i < M ; i++){
		deg[A[i]]++;
		deg[B[i]]++;
	}
	for(int i = 0 ; i < N ; i++){
		if(deg[i] >= N - LOG - 50 - 1){
			type[i] = 1;
		}
	}
	for(int i = 0 ; i < M ; i++){
		if(type[A[i]] == 1)	deg2[B[i]]++;
		if(type[B[i]] == 1)	deg2[A[i]]++;
	}
	int n = 0 , m = 0;
	for(int i = 0 ; i < N ; i++){
		if(type[i] == 1)	continue;
		if(deg2[i] >= 100){
			type[i] = 0;
			n++;
		}
		else if(deg2[i] >= 50){
			type[i] = 2;
		}
		else{
			type[i] = 3;
		}
	}
	vector<pii> E;
	for(int i = 0 ; i < M ; i++){
		if(type[A[i]] > type[B[i]])	swap(A[i] , B[i]);
		if(type[A[i]] == 0 && type[B[i]] == 3){
			ind[A[i]] |= (1 << deg2[B[i]]);
		}
		if(type[B[i]] == 0){
			E.push_back({A[i] , B[i]});
		}
	}
	m = SZ(E);
	InitMap(n , m);
	for(pii i : E){
		MakeMap(ind[i.X] , ind[i.Y]);
	}
}

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