Submission #731315

#	Time	Username	Problem	Language	Result	Execution time	Memory
731315		myrcella	Airline Route Map (JOI18_airline)	C++17	100 / 100	684 ms	33536 KiB

Alice

//by szh
#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}

#include "Alicelib.h"

const int maxn = 2020;

int id[maxn];

void Alice( int N, int M, int A[], int B[] ){
	int cur = 0,tot=1,ecnt=0;
	rep(i,1,N+1) {
		while (tot == (1<<cur)) cur++,tot++;
		id[i] = tot++;
		ecnt += __builtin_popcount(id[i]);
	}
	InitG(N+12,M+9+10+1+ecnt);
	rep(i,0,M) {
		MakeG(i,A[i],B[i]);
	}
	rep(i,0,9) MakeG(i+M,N+i,N+i+1);
	rep(i,0,10) MakeG(i+M+9,N+10,N+i);
	MakeG(M+9+10,N+10,N+11);
	int tmp = M+9+10+1;
	rep(i,1,N+1) {
		rep(j,0,10) if ((id[i]>>j)&1) MakeG(tmp++,i-1,N+j);
	}
}

Bob

//by szh
#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}

#include "Boblib.h"

int deg[2020];

vector <int> edge[2020];
vector <pii> ans;
int mp[2020];
int p[2020];
bool mark[2020];
int val[2020];
int con[2020][2020];

void Bob( int V, int U, int C[], int D[] ){
	rep(i,0,U) {
		deg[C[i]]++;
		deg[D[i]]++;
		edge[C[i]].pb(D[i]);
		edge[D[i]].pb(C[i]);
		con[C[i]][D[i]] = con[D[i]][C[i]] = 1;
	}
	int hi = -1;
	rep(i,0,V) if (deg[i]==1) hi = i;
	assert(hi!=-1);
	int hii = edge[hi][0];
	mark[hii] = mark[hi] = 1;
	vector <int> node;
	int st=-1;
	for (int v:edge[hii]) {
		if (v==hi) continue;
		mark[v] = 1;
		int cnt = 0;
		for (int to:edge[v]) {
			if (con[to][hii]) cnt++;
			if (cnt==2) break;
		}
		assert (cnt==2 or cnt==1);
		if (cnt==1 and (st==-1 or deg[v]>deg[st])) st = v;
	}
	assert(st!=-1);
	int lst = -1;
	node.pb(st);p[st] = 0;
//	debug(hi);debug(hii);
	rep(i,0,9) {
		int to = -1;
		for (int v:edge[st]) if (v!=lst and v!=hii and mark[v]) to = v;
		p[to] = SZ(node);
		node.pb(to);
		mark[to] =1;
		lst = st, st = to;
//		debug(st);
	}
	rep(i,0,U) {
		if (mark[C[i]]==0 and mark[D[i]]==0) ans.pb({C[i],D[i]});
		else if (mark[C[i]]==0 and mark[D[i]]==1) val[C[i]] += (1<<p[D[i]]);
		else if (mark[D[i]]==0 and mark[C[i]]==1) val[D[i]] += (1<<p[C[i]]);
	}
	rep(i,0,SZ(ans)) ans[i].fi = val[ans[i].fi],ans[i].se = val[ans[i].se];
	int cur = 0,tot=1;
	rep(i,0,V-12) {
		while (tot == (1<<cur)) cur++,tot++;
		mp[tot++] = i;
	}
	InitMap(V-12,SZ(ans));
	rep(i,0,SZ(ans)) MakeMap(mp[ans[i].fi],mp[ans[i].se]);
}

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