Submission #1205354

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205354		thelegendary08	Airline Route Map (JOI18_airline)	C++17	88 / 100	229 ms	23352 KiB

Alice

#include "Alicelib.h"
#include <cassert>
#include <cstdio>
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define vi vector<int>
#define vvi vector<vector<int>>
#define pii pair<int, int>
#define vpii vector<pair<int, int>>
#define vc vector<char>
#define vb vector<bool>
#define mii map<int,int>
#define f0r(i,n) for(int i=0;i<n;i++)
#define FOR(i,k,n) for(int i=k;i<n;i++)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define in(a) int a; cin>>a
#define in2(a,b) int a,b; cin>>a>>b
#define in3(a,b,c) int a,b,c; cin>>a>>b>>c
#define in4(a,b,c,d) int a,b,c,d; cin>>a>>b>>c>>d
#define vin(v,n); vi v(n); f0r(i,n){cin>>v[i];}
#define out(a) cout<<a<<'\n'
#define out2(a,b) cout<<a<<' '<<b<<'\n'
#define out3(a,b,c) cout<<a<<' '<<b<<' '<<c<<'\n'
#define out4(a,b,c,d) cout<<a<<' '<<b<<' '<<c<<' '<<d<<'\n'
#define pout(a) cout<<a.first<<' '<<a.second<<'\n'
#define vout(v) for(auto u : v){cout<<u<<' ';} cout<<'\n'
#define dout(a) cout<<a<<' '<<#a<<'\n'
#define dout2(a,b) cout<<a<<' '<<#a<<' '<<b<<' '<<#b<<'\n'
#define yn(x); if(x){cout<<"YES"<<'\n';}else{cout<<"NO"<<'\n';}
const int leg = 1e9 + 7;
const int mod = 998244353;
using namespace std;

void Alice( int N, int M, int A[], int B[] ){
	/*
	InitG( 3, 2 );
	MakeG( 1, 2 );
	MakeG( 1, 3 );
	*/
	if(N <= 3){
		if(N == 1){
			InitG(1, 0);
		}
		else{
			if(N == 2){
				if(M == 0)InitG(2, 0);
				else InitG(3, 0);
			}
			else{
				int cur = 4;
				f0r(i, M){
					int sum = A[i] + B[i];
					if(sum == 1)cur++; //draw 0-1
					if(sum == 2)cur+=2; //draw 0-2
					if(sum == 3)cur+=4; //draw 1-2
				}
				InitG(cur, 0);
			}
		}
	}
	else{
		int cnt = 0;
		mii encode;
		mii decode;
		vb visd((1 << 11));
		int stupid = 0;
		f0r(i, 11){
			stupid += (1 << i);
		}
		visd[stupid] = 1;
		encode[0] = stupid;
		decode[stupid] = 0;
		stupid-=2;
		visd[stupid] = 1;
		encode[1] = stupid;
		decode[stupid] = 1;
		stupid+=2;
		stupid-=4;
		visd[stupid] = 1;
		encode[2] = stupid;
		decode[stupid] = 2;
		stupid += 4;
		stupid -= 8;
		visd[stupid] = 1;
		encode[3] = stupid;
		decode[stupid] = 3;
		cnt = 4;
		f0r(i, (1<<11)){
			if(visd[i])continue;
			int on = 0;
			f0r(j, 11){
				if((1 << j) & i)on++;
			}
			
			if(on >= 6){
				encode[cnt] = i;
				decode[i] = cnt; 
				cnt++;
			}
		}
		
		vpii edges;
		f0r(i, M){
			edges.pb(mp(A[i], B[i]));
		}
		//N to N + 10 
		//N + 11 to N + 13 as dummy
		f0r(i, N){
			int ec = encode[i];
			f0r(j, 11){
				if(ec & (1 << j)){
					edges.pb(mp(i, N + j));
				}
			}
		}
		
		FOR(i, N, N + 10){
			edges.pb(mp(i, i+1));
		}
		FOR(i, N, N + 5){
			edges.pb(mp(i, N + 11));
		}
		FOR(i, N + 5, N + 8){
			edges.pb(mp(i, N + 12));
		}
		FOR(i, N + 8, N + 11){
			edges.pb(mp(i, N + 13));
		}
		vi deg(N + 14);
		for(auto u : edges){
			deg[u.first]++; deg[u.second]++;
		}
		FOR(i, N, N+11){
			// cout<<deg[i]<<' ';
		}
		// cout<<'\n';
		InitG(N + 14, edges.size());
		int ct = 0;
		for(auto u : edges){
			MakeG(ct, u.first, u.second);
			ct++;
		}
	}
	
}

Bob

#include "Boblib.h"
#include <cassert>
#include <cstdio>
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define vi vector<int>
#define vvi vector<vector<int>>
#define pii pair<int, int>
#define vpii vector<pair<int, int>>
#define vc vector<char>
#define vb vector<bool>
#define mii map<int,int>
#define f0r(i,n) for(int i=0;i<n;i++)
#define FOR(i,k,n) for(int i=k;i<n;i++)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define in(a) int a; cin>>a
#define in2(a,b) int a,b; cin>>a>>b
#define in3(a,b,c) int a,b,c; cin>>a>>b>>c
#define in4(a,b,c,d) int a,b,c,d; cin>>a>>b>>c>>d
#define vin(v,n); vi v(n); f0r(i,n){cin>>v[i];}
#define out(a) cout<<a<<'\n'
#define out2(a,b) cout<<a<<' '<<b<<'\n'
#define out3(a,b,c) cout<<a<<' '<<b<<' '<<c<<'\n'
#define out4(a,b,c,d) cout<<a<<' '<<b<<' '<<c<<' '<<d<<'\n'
#define pout(a) cout<<a.first<<' '<<a.second<<'\n'
#define vout(v) for(auto u : v){cout<<u<<' ';} cout<<'\n'
#define dout(a) cout<<a<<' '<<#a<<'\n'
#define dout2(a,b) cout<<a<<' '<<#a<<' '<<b<<' '<<#b<<'\n'
#define yn(x); if(x){cout<<"YES"<<'\n';}else{cout<<"NO"<<'\n';}
using namespace std;

void Bob( int V, int U, int C[], int D[] ){
	/*
	InitMap( 3, 2 );
	MakeMap( 1, 2 );
	MakeMap( 1, 3 );
	*/
	
	if(U == 0){
		if(V == 1){
			InitMap(1, 0);
		}
		else if(V == 2){
			InitMap(2, 0);
		}
		else if(V == 3){
			InitMap(2, 1);
			MakeMap(0, 1);
		}
		else{
			int thing = V - 4;
			vpii edges;
			if(thing & 1){
				edges.pb(mp(0, 1));
			}
			if(thing & 2){
				edges.pb(mp(0, 2));
			}
			if(thing & 4){
				edges.pb(mp(1,2));
			}
			
			InitMap(3, edges.size());
			for(auto u : edges){
				MakeMap(u.first,u.second);
			}
		}
	}
	else{
		int cnt = 0;
		mii encode;
		mii decode;
		vb visd((1 << 11));
		int stupid = 0;
		f0r(i, 11){
			stupid += (1 << i);
		}
		visd[stupid] = 1;
		encode[0] = stupid;
		decode[stupid] = 0;
		stupid-=2;
		visd[stupid] = 1;
		encode[1] = stupid;
		decode[stupid] = 1;
		stupid+=2;
		stupid-=4;
		visd[stupid] = 1;
		encode[2] = stupid;
		decode[stupid] = 2;
		stupid += 4;
		stupid -= 8;
		visd[stupid] = 1;
		encode[3] = stupid;
		decode[stupid] = 3;
		cnt = 4;
		
		f0r(i, (1<<11)){
			if(visd[i])continue;
			int on = 0;
			f0r(j, 11){
				if((1 << j) & i)on++;
			}
			
			if(on >= 6){
				encode[cnt] = i;
				decode[i] = cnt; 
				cnt++;
			}
		}
		
		vi deg(V);
		vvi adj(V);
		f0r(i, U){
			adj[C[i]].pb(D[i]);
			adj[D[i]].pb(C[i]);
			deg[C[i]]++;
			deg[D[i]]++;
		}
		vi things;
		int five;
		f0r(i, V){
			if(deg[i] <= 5)things.pb(i);
			if(deg[i] == 5)five = i;
		}
		// vout(things);
		vi sus;
		vb issus(V);
		for(auto u : things){
			for(auto v : adj[u]){
				sus.pb(v);
				issus[v] = 1;
			}
		}
		
		map<int,set<int>>susadj;
		mii susdeg;
		for(auto u : sus){
			for(auto v : adj[u]){
				if(issus[v]){
					susadj[u].insert(v);
					susadj[v].insert(u);
				}
			}
		}
		for(auto u : susadj){
			susdeg[u.first] = u.second.size();
		}
		
		int st;
		for(auto u : susdeg){
			if(u.second == 1 && find(adj[u.first].begin(), adj[u.first].end(), five) != adj[u.first].end()){
				st = u.first;
			}
		}
		
		int cur = st;
		vi gw; 
		gw.pb(cur);
		set<int>vis;
		vis.insert(cur);
		while(1){
			bool f = 0;
			for(auto u : susadj[cur]){
				if(!vis.count(u)){
					cur = u; vis.insert(u); f=1; break;
				}
			}
			if(!f)break;
			gw.pb(cur);
			
		}
		mii val;
		f0r(i, gw.size()){
			val[gw[i]] = (1 << i);
		}
		// vout(gw);
		vi label(V, 0);
		f0r(i, gw.size()){
			for(auto u : adj[gw[i]]){
				if(deg[u] > 5 && !issus[u]){
					label[u] += val[gw[i]];
				}
			}
		}
		
		vpii edges;
		f0r(i, U){
			// out2(C[i], D[i]);
			if(label[C[i]] != 0 && label[D[i]] != 0){
				int r1 = decode[label[C[i]]];
				int r2 = decode[label[D[i]]];
				edges.pb(mp(r1, r2));
			}
		}
		// vout(label);
		/*
		out(edges.size());
		for(auto u : edges){
			out2(u.first, u.second);
		}
		*/
		InitMap(V - 14, edges.size());
		for(auto u : edges){
			MakeMap(u.first, u.second);
			// out2(u.first, u.second);
		}
		
	}
	
	
}

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