Submission #1184199

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184199		amine_aroua	Airline Route Map (JOI18_airline)	C++20	37 / 100	58 ms	22260 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<vector<int>> group(N);
	int cnt = 0;
	for(int i = 0 ; i < N ; i++)
	{
		for(int j = 0 ;j < i + 3 ; j++)
		{
			group[i].push_back(cnt++);
		}
	}
	vector<pair<int ,int>> edgs;
	for(int i = 0 ; i < N ; i++)
	{
		int s = (int)group[i].size();
		for(int j = 0 ; j < s ; j++)
		{
			edgs.push_back({group[i][j] , group[i][(j + 1) % s]});
		}
	}
	for(int i = 0 ; i < M ; i++)
	{
		edgs.push_back({group[A[i]][0] , group[B[i]][0]});
	}
	InitG(cnt , (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;
static vector<bool> vis;
static vector<vector<int>> adj;
static vector<int> id;
static vector<int> cumul;
static void dfs(int x)
{
	if(vis[x])
		return ;
	vis[x] = 1;
	cumul.push_back(x);
	if((int)adj[x].size() > 2)
		return ;
	for(auto u : adj[x])
		dfs(u);
}
void Bob( int V, int U, int C[], int D[] ){
	vis.assign(V , 0);
	adj.assign(V , {});
	id.assign(V , 0);
	cumul.clear();
	for(int i = 0 ; i < U ; i++)
	{
		adj[C[i]].push_back(D[i]);
		adj[D[i]].push_back(C[i]);
	}
	int mx = 0;
	for(int i = 0 ; i < V ; i++)
	{
		if((int)adj[i].size() == 2 && !vis[i])
		{
			dfs(i);
			int cte = (int)cumul.size() - 3;
			mx = max(mx , cte);
			for(auto c : cumul)
			{
				id[c] = cte;
			}
			cumul.clear();
		}
	}
	vector<pair<int ,int>> edgs;
	for(int i = 0 ; i < U ; i++)
	{
		if((int)adj[C[i]].size() > 2 && (int)adj[D[i]].size() > 2)
		{
			edgs.push_back({id[C[i]] , id[D[i]]});
		}
	}
	InitMap(mx + 1 , (int)edgs.size());
	for(auto p : edgs)
	{
		MakeMap(p.first , p.second);
	}
}

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