제출 #1306132

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1306132		nicolo_010	항공 노선도 (JOI18_airline)	C++20	100 / 100	234 ms	54128 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+11; i++) {
	    if (i-n <= 9) {
	        int b = i-n;
	        for (int j=0; j<n; j++) {
	            if (j&(1<<(b))) edges.push_back({i, j});
	        }
	        if (i-n < 9)edges.push_back({i, i+1});
	    }
	    else {
	        for (int j=0; j<n; j++) {
	            edges.push_back({i, j});
	        }
	        edges.push_back({i, i+1});
	    }
	}
	m = edges.size();
	InitG(n+12, 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;


void Bob( int v, int u, int C[], int D[] ){
    vector<vector<int>> adj(v);
    vector<vector<int>> grid(v, vector<int>(v, 0));
	adj.assign(v, {});
	int n = v-12;
	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);
		grid[a][b] = 1;
		grid[b][a] = 1;
	}
	int node;
	vector<bool> vis(v, false);
	vector<bool> invalid(v, false);
	for (int i=0; i<v; i++) {
	    if (adj[i].size()==1 && adj[adj[i][0]].size() == n+1) {
	        node = adj[i][0];
	        break;
	    }
	}
	invalid[node] = true;
	int bit = node;
	for (int i=0; i<v; i++) {
	    if (!grid[i][node] && i != node) {
	        invalid[i] = true;
	        if (adj[i].size() <= adj[bit].size()) bit = i;
	    }
	}
	vector<int> id(v, 0);
	for (int i=9; i>=0; i--) {
	    vis[bit] = true;
	    for (auto x : adj[bit]) id[x] += (1<<i);
	    for (auto x : adj[bit]) {
	        if (invalid[x] && !vis[x]) {
	            bit = x;
	            break;
	        }
	    }
	}
	vector<vector<int>> edges;
	for (int i=0; i<v; i++) {
	    for (int j=i+1; j<v; j++) {
	        if (grid[i][j] && !invalid[i] && !invalid[j]) {
	            edges.push_back({id[i], id[j]});
	        }
	    }
	}
	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: 63 / 63