제출 #1306129

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1306129		nicolo_010	항공 노선도 (JOI18_airline)	C++20	37 / 100	228 ms	50204 KiB

Alice

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

const int block = 100;

void Alice( int n, int m, int A[], int B[] ){
	vector<vector<int>> edges(m);
	for (int i=0; i<m; i++) {
		edges[i] = {A[i], B[i]};
	}
	for (int i=n; i<n+block; i++) {
		for (int j=i+1; j<n+block; j++) {
			edges.push_back({i, j});
		}
	}
	for (int i=n; i<n+block; i++) {
		if (i-n >= n) break;
		for (int j=i-n; j < n; j++) {
			edges.push_back({j, i});
		}
	}
	m = edges.size();
	InitG(n+block, m);
	for (int i=0; i<m; i++) {
		MakeG(i, edges[i][0], edges[i][1]);
	}
}

Bob

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

const int block = 100;

vector<vector<int>> adj;

bool cmp(int a, int b) {
	return adj[a].size()>adj[b].size();
}

void Bob( int v, int u, int C[], int D[] ){
	adj.assign(v, {});
	for (int i=0; i<u; i++) {
		int a = C[i];
		int b = D[i];
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	vector<int> a(v);
	for (int i=0; i<v; i++) {
		a[i] = i;
	}
	sort(a.begin(), a.end(), cmp);
	int n = v-block;
	vector<int> id(v, 0);
	vector<bool> vis(v, false);
	for (int i=0; i<block; i++) {
		vis[a[i]] = true;
	}
	for (int i=0; i<n; i++) {
		for (auto x : adj[a[i]]) {
			if (!vis[x]) id[x]++;
		}
	}
	map<vector<int>, int> mp;
	vector<vector<int>> edges;
	for (int i=0; i<v; i++) {
		if (vis[i]) continue;
		for (auto x : adj[i]) {
			if (vis[x]) continue;
			if (mp.count({id[i]-01, id[x]-1}) || mp.count({id[x]-1, id[i]-1})) continue;
		    edges.push_back({id[i]-1, id[x]-1});
		    mp[{id[i]-1, id[x]-1}] = 1;
		}
	}
	int m = edges.size();
	InitMap(n, m);
	for (int i=0; i<m; i++) {
		MakeMap(edges[i][0], edges[i][1]);
	}
}

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