Submission #595140

#	Time	Username	Problem	Language	Result	Execution time	Memory
595140		Koosha_mv	Airline Route Map (JOI18_airline)	C++14	100 / 100	743 ms	25396 KiB

Alice

#include "Alicelib.h"
#include <cassert>
#include <cstdio>
#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<x.F<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first

const int N=1e6+99,lg=10;

int n,m,cnt;
vector<pair<int,int>> edge;

void Alice(int _n,int _m,int A[],int B[] ){
	n=_n,m=_m;
	f(i,0,n){
		f(j,0,lg){
			if(bit(i+1,j)){
				edge.pb({i,n+j});
			}
		}
	}
	f(j,0,lg-1) edge.pb({n+j,n+j+1});
	f(i,0,n+lg) edge.pb({i,n+lg});
	f(i,n,n+lg) edge.pb({i,n+lg+1});
	InitG(n+lg+2,m+edge.size());
	f(i,0,m) MakeG(cnt++,A[i],B[i]);
	for(auto p : edge) MakeG(cnt++,p.F,p.S);
}
/*void Alice( int N, int M, int A[], int B[] ){
	InitG(3,2);
	MakeG(0,0,1);
	MakeG(1,1,2);
}*/

Bob

#include "Boblib.h"
#include <cassert>
#include <cstdio>
#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<x.F<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first

const int N=1111;

int g[N][N],deg[N],mark[N],ans[N];

void Bob(int n, int m,int A[],int B[]){
	/*cout<<n<<" - "<<m<<endl;
	f(i,0,m){
		cout<<A[i]<<" "<<B[i]<<endl;
	}*/
	int x=0;
	f(i,0,m) deg[A[i]]++,deg[B[i]]++,g[A[i]][B[i]]=g[B[i]][A[i]]=1; 	
	f(i,0,n){
		if(deg[i]>deg[x]) x=i;
	}
	ans[x]=-1;
	f(i,0,n){
		if(i!=x && g[i][x]==0){
			x=i;
			break ;
		}
	}
	ans[x]=-1;
	vector<int> vec;
	f(i,0,n){
		if(g[x][i]==1){
			ans[i]=-1;
			mark[i]=1;
		}
	}
	f(i,0,n){
		if(mark[i]){
			int deg=0;
			f(j,0,n){
				if(mark[j] && g[i][j]){
					deg++;
				}
			}
			if(deg==1){
				x=i;
				break ;
			}
		}
	}
	for(int u=x,b=1;b;){
		mark[u]=b=0;
		vec.pb(u);
		f(i,0,n) if(g[u][i] && mark[i]){
			u=i,b=1;
			break ;
		}
	}
	int deg0=0,deg1=0;
	f(i,0,n){
		deg0+=g[vec[0]][i];
		deg1+=g[vec.back()][i];
	}
	if(deg0<deg1){
		reverse(all(vec));
	}
	vector<pair<int,int>> edge;
	f(i,0,n){
		if(ans[i]==-1) continue ;
		f(j,0,vec.size()) ans[i]^=g[i][vec[j]]*(1<<j);
	}
	f(i,0,m){
		if(ans[A[i]]>0 && ans[B[i]]>0){
			edge.pb({ans[A[i]]-1,ans[B[i]]-1});
		}
	}
	InitMap(n-12,edge.size());
	for(auto p : edge){
		MakeMap(p.F,p.S);
	}
}

Compilation message (stderr)

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:11:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   88 |   f(j,0,vec.size()) ans[i]^=g[i][vec[j]]*(1<<j);
      |     ~~~~~~~~~~~~~~             
Bob.cpp:88:3: note: in expansion of macro 'f'
   88 |   f(j,0,vec.size()) ans[i]^=g[i][vec[j]]*(1<<j);
      |   ^

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