Submission #1185512

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185512		amine_aroua	Airline Route Map (JOI18_airline)	C++20	100 / 100	230 ms	23232 KiB

Alice

#include "Alicelib.h"
#include <cassert>
#include <cstdio>
#include<bits/stdc++.h>
using namespace std;
void Alice( int N, int M, int A[], int B[] ){
	vector<pair<int ,int>> edgs;
	for(int i = 0 ; i < M ; i++)
	{
		edgs.push_back({A[i] , B[i]});
	}
	edgs.push_back({N + 1 , N});
	for(int i = 0 ; i < N ; i++)
	{
		edgs.push_back({N , i});
	}
	for(int i = 0 ; i < N ; i++)
	{
		for(int j = 0 ; j <= 9 ; j++)
		{
			if((1<<j) & i)
			{
				edgs.push_back({j + N + 2 , i});
			}
		}
	}
	for(int j = 0 ; j <= 8 ; j++)
	{
		edgs.push_back({j + N + 2 , j + N + 3});
	}
	InitG(N + 12 , (int)edgs.size());
	for(int i = 0 ; i < (int)edgs.size() ; i++)
	{
		MakeG(i , edgs[i].first , edgs[i].second);
	}
}

Bob

#include "Boblib.h"
#include <cassert>
#include <cstdio>
#include<bits/stdc++.h>
using namespace std;
int nb = -1;
void dfs(int x , vector<bool> &vis , vector<bool> &original , vector<int> &label , vector<vector<int>> &adj)
{
	if(vis[x])
		return;
	vis[x] = 1;
	nb++;
	for(auto u : adj[x])
	{
		if(original[u])
		{
			label[u]|=(1<<nb);
		}
	}
	for(auto u : adj[x])
	{
		dfs(u , vis , original , label , adj);
	}
}
void Bob( int V, int U, int C[], int D[] ){
	nb = -1;
	int N = V - 12;
	vector<vector<int>> adj(V);
	vector<int> label(V);
	vector<bool> original(V);
	vector<bool> vis(V);
	for(int i = 0 ; i < U ; i++)
	{
		adj[C[i]].push_back(D[i]);
		adj[D[i]].push_back(C[i]);
	}
	int Node  = 0 , extra = 0;
	for(int i = 0 ; i < V ; i++)
	{
		if((int)adj[i].size() == 1 && (int)adj[adj[i][0]].size() ==N + 1)
		{
			Node = adj[i][0];
			extra = i;
		}
	}
	vis[Node] = 1;
	for(auto i : adj[Node])
	{
		vis[i] = 1;
		if(i != extra)
		{
			original[i] = 1;
		}
	}
	int strt = -1;
	int nbs = -1;
	for(int i = 0 ; i < V ; i++)
	{
		if(i != Node && i != extra && !original[i])
		{
			int nb = 0;
			for(auto j : adj[i])
			{
				nb+=original[j];
			}
			if(nb > nbs && (int)adj[i].size() == nb + 1)
			{
				strt = i;
				nbs = nb;
			}
		}
	}

	dfs(strt , vis , original  , label , adj);
	vector<pair<int ,int>> edgs;
	for(int i = 0 ; i < U ; i++)
	{
		if(original[C[i]] && original[D[i]])
		{
			edgs.push_back({label[C[i]] , label[D[i]]});
		}
	}
	InitMap(N , (int)edgs.size());
	for(int i = 0 ; i < (int)edgs.size() ; i++)
	{
		MakeMap(edgs[i].first , edgs[i].second);
	}
}

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