Submission #1202169

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202169		8pete8	Airline Route Map (JOI18_airline)	C++20	100 / 100	168 ms	23080 KiB

Alice

#include "Alicelib.h"
#include <cassert>
#include <cstdio>
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
int deg[1001];
int c=0,bro=0;;
void create(int a,int b){
	bro++;
	MakeG(c++,a,b);
}
void Alice( int N, int M, int A[], int B[] ){
	for(int i=0;i<M;i++)deg[A[i]]++,deg[B[i]]++;
	int cnt=0;
	for(int i=0;i<N;i++){
		for(int j=0;j<10;j++)if((i+1)&(1LL<<j))cnt++;
	}
	InitG(N+12,M+cnt+N+10);

	int C=N;
	for(int i=0;i<M;i++)create(A[i],B[i]);
	//cycle
	for(int i=0;i<9;i++){
		create(C,C+1);
		C++;
	}
	C++;
	create(C,C+1);
	C++;
	for(int i=0;i<N;i++)create(i,C);

	for(int i=0;i<N;i++)for(int j=0;j<10;j++)if((i+1)&(1LL<<j)){
		create(i,j+N);
	}
}

/*
4 3
0 1
0 2
0 3
*/

Bob

#include "Boblib.h"
#include <cassert>
#include <cstdio>
#include<bits/stdc++.h>
#define pb push_back
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
using namespace std;
vector<int>adj[2002];
int lab[2002];
int val[2002],mark[2002];
vector<int>sp;
void dfs(int cur){
	mark[cur]=1;
	sp.pb(cur);
	for(auto j:adj[cur])if(!mark[j])dfs(j);
}
void Bob( int V, int U, int C[], int D[] ){
	int node=-1;
	for(int i=0;i<U;i++){
		adj[C[i]].pb(D[i]);
		adj[D[i]].pb(C[i]);
	}
	for(int i=0;i<V;i++){
		if(adj[i].size()==1&&adj[adj[i][0]].size()==V-11){
			node=i;
		}
	}
	if(V==13)return void(InitMap(1,0));
	for(int i=0;i<V;i++)val[i]=-1;
	for(auto j:adj[node])node=j;
	mark[node]=1;
	for(auto j:adj[node])mark[j]=1;
	for(int i=0;i<V;i++)if(!mark[i]){
		int c=0;
		for(auto j:adj[i])if(!mark[j])c++;
		if(c==1)dfs(i);
	}
	if(sp.size()!=10)assert(0);
	if(adj[sp[0]].size()<adj[sp.back()].size())reverse(all(sp));
	for(int j=0;j<sp.size();j++)val[sp[j]]=j;
	vector<pii>ans;
	for(int i=0;i<V;i++)if(val[i]==-1&&i!=node&&adj[i].size()>1){
		int x=0;
		for(auto j:adj[i])if(val[j]!=-1)x+=(1LL<<val[j]);
		lab[i]=x;
		for(auto j:adj[i])if(val[j]==-1&&j!=node&&j<i){
			ans.pb({lab[i],lab[j]});
		}
	}
	InitMap(V-12,ans.size());
	for(auto i:ans)MakeMap(i.f-1,i.s-1);
}

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