Submission #1246996

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246996		PlayVoltz	항공 노선도 (JOI18_airline)	C++20	100 / 100	193 ms	23172 KiB

Alice

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

#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

void Alice(int n, int m, int a[], int b[]){
	if (n==1||n==2){
		InitG(n, m);
		if (m)MakeG(0, 0, 1);
		return;
	}
	vector<pii> res;
	for (int i=0; i<m; ++i)res.pb(mp(a[i], b[i]));
	for (int i=0; i<n; ++i)for (int j=0; j<10; ++j)if (i&(1<<j))res.pb(mp(i, n+j));
	for (int i=0; i<10; ++i)res.pb(mp(n+i, n+10));
	for (int i=0; i<n+10; ++i)res.pb(mp(i, n+11));
	for (int i=0; i<9; ++i)res.pb(mp(n+i, n+i+1));
	InitG(n+12, res.size());
	for (int i=0; i<res.size(); ++i)MakeG(i, res[i].fi, res[i].se);
}

Bob

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

#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

void Bob(int n, int m, int c[], int d[]){
	if (n==1){
		InitMap(1, 0);
		return;
	}
	if (n==2){
		InitMap(n, m);
		if (m==1)MakeMap(1, 0);
		return;
	}
	vector<int> deg(n, 0);
	for (int i=0; i<m; ++i)++deg[c[i]], ++deg[d[i]];
	int fat, mx=-1, par, node=-1, d1=0, d2=0;
	vector<vector<bool> > graph(n, vector<bool>(n, 0));
	for (int i=0; i<n; ++i)if (deg[i]>mx)mx=deg[i], fat=i;
	for (int i=0; i<m; ++i)graph[c[i]][d[i]]=graph[d[i]][c[i]]=1;
	for (int i=0; i<n; ++i)if (!graph[i][fat]&&i!=fat)par=i;
	for (int i=0; i<n; ++i)if (graph[par][i]){
		int count=0;
		for (int j=0; j<n; ++j)if (graph[par][j]&&graph[i][j])++count;
		if (count==1)node=i;
	}
	vector<bool> visited(n, 0);
	vector<int> vect;
	bool loop=1;
	while (loop){
		vect.pb(node);
		visited[node]=1;
		loop=0;
		for (int i=0; i<n; ++i)if (graph[i][node]&&!visited[i]&&graph[par][i]){
			node=i, loop=1;
			break;
		}
	}
	for (int i=0; i<n; ++i)d1+=graph[vect[0]][i], d2+=graph[vect[9]][i];
	if (d1<d2)reverse(vect.begin(), vect.end());
	vector<pii> ans;
	for (int i=0; i<m; ++i)if (!graph[par][c[i]]&&!graph[par][d[i]]&&c[i]!=fat&&d[i]!=fat&&c[i]!=par&&d[i]!=par){
		int a=0, b=0;
		for (int j=0; j<10; ++j)if (graph[c[i]][vect[j]])a+=(1<<j);
		for (int j=0; j<10; ++j)if (graph[d[i]][vect[j]])b+=(1<<j);
		ans.pb(mp(a, b));
	}
	InitMap(n-12, ans.size());
	for (auto a:ans)MakeMap(a.fi, a.se);
}

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