Submission #1214569

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214569		mychecksedad	Airline Route Map (JOI18_airline)	C++20	37 / 100	89 ms	44236 KiB

Alice

#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;
	vi deg(n);
	for(int i = 0; i < n; ++i){
		for(int j = i + 1; j < n; ++j){
			if(E[i][j]){
				P.pb({i, j});
				deg[i]++;
				deg[j]++;
			}
		}
	}
	for(int i = 0; i < n; ++i){
		int cur = n;
		for(int j = 0; j < i + n - deg[i]; ++j){
			P.pb({cur++, i});
		}
	}
	for(int i = n; i < 3*n+1; ++i){
		for(int j = i+1; j < 3*n+1; ++j) P.pb({i, j});
	}
	int cnt = 0;
	InitG(n * 3 + 1, int(P.size()));
	for(auto [x, y]: P){
		// cerr << x << ' ' << y << '\n';
		MakeG(cnt++, x, y);
	}
}

Bob

#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 Bob( int nn, int mm, int C[], int D[] ){
	int n = (nn - 1) / 3;
	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;
		// cerr << C[i] << ' ' << D[i] << '\n';
	}
	vi node(n);
	for(int i = 0; i < nn; ++i){
		// cerr << deg[i] << ' ';
		if(deg[i] - n < n){
			node[deg[i] - n] = i;
		}
	}
	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});
		}
	}
	// cerr << P.size() << '\n';
	InitMap(n, int(P.size()));
	for(auto [x, y]: P) MakeMap(x, y);
}

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