Submission #567901

#	Time	Username	Problem	Language	Result	Execution time	Memory
567901		errorgorn	Flights (JOI22_flights)	C++17	69 / 100	496 ms	5304 KiB

Ali

#include "Ali.h"

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

#define int long long
#define ii pair<int,int>
#define fi first
#define se second
#define endl '\n'

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound

#define rep(x,s,e) for (int x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e))?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

namespace {

int read(string s,int i,int j){
	int res=0;
	rep(x,i,j+1){
		res<<=1;
		if (s[x]=='1') res++;
	}
	
	return res;
}

string write(int i,int j){
	string s="";
	
	rep(x,0,j){
		s+='0'+(i&1);
		i>>=1;
	}
	
	reverse(all(s));
	return s;
}

ii trans2(int i){
	int IDX=0;
	rep(y,0,10005){
		rep(x,0,y+1){
			if (IDX==i) return {x,y};
			IDX++;
		}
	}
	
	return {-1,-1};
}

const int BUC=7;
const int BS=2*BUC-1;

int n;
vector<int> al[10005];
int d[10005];
int pp[10005];
vector<int> grp[10005];
vector<vector<int> > v;

void dfs(int i,int p){
	for (auto it:al[i]){
		if (it==p) continue;
		
		d[it]=d[i]+1;
		pp[it]=i;
		dfs(it,i);
		grp[i].insert(grp[i].end(),all(grp[it]));
	}
	
	grp[i].pub(i);
	
	if (sz(grp[i])>=BUC || p==-1){
		v.pub(grp[i]);
		grp[i].clear();
	}
}

int id[10005];
set<int> s;
string seq[10005];

int IDX1,IDX2;

void dfs2(int i,int p){
	id[i]=IDX1*BS+IDX2;
	grp[IDX1].pub(i);
	if (p!=-1) seq[IDX1]+='0';
	IDX2++;
	
	for (auto it:al[i]){
		if (it==p || !s.count(it)) continue;
		dfs2(it,i);
	}
	
	if (p!=-1) seq[IDX1]+='1';
}

int dist(int i,int j){ //damn lazy
	if (d[i]<d[j]) swap(i,j);
	
	int res=0;
	while (i!=j){
		if (d[i]==d[j]){
			res+=2;
			i=pp[i],j=pp[j];
		}
		else{
			res++;
			i=pp[i];
		}
	}
	
	return res;
}

}

void Init(signed N, vector<signed> U, vector<signed> V) {
	rep(x,0,10005) al[x].clear();
	rep(x,0,10005) d[x]=0;
	rep(x,0,10005) pp[x]=-1;
	rep(x,0,10005) grp[x].clear();
	v.clear();
	rep(x,0,10005) id[x]=0;
	rep(x,0,10005) seq[x]="";
	
	n=N;
	rep(x,0,n-1){
		al[U[x]].pub(V[x]);
		al[V[x]].pub(U[x]);
	}
	
	rep(x,0,n) if (sz(al[x])==1){
		//cout<<"debug: "<<x<<endl;
		dfs(x,-1);
		break;
	}
	
	for (auto &it:v) sort(all(it),[](int i,int j){ return d[i]<d[j]; });
	sort(all(v),[](vector<int> i,vector<int> j){
		return d[i[0]]<d[j[0]];
	});
	
	rep(x,0,10005) grp[x].clear();
	
	IDX1=0;
	for (auto it:v){
		s=set<int>(all(it));
		IDX2=0;
		dfs2(it[0],-1);
		
		//for (auto it2:grp[IDX1]) cout<<it2<<" "; cout<<endl;
		//cout<<seq[IDX1]<<endl;
		
		while (sz(seq[IDX1])<2*(BS-1)) seq[IDX1]+='0';
		IDX1++;
	}
	
	//rep(x,0,n) cout<<id[x]<<" "; cout<<endl;
	rep(x,0,n) SetID(x,id[x]);
}

string SendA(string S) {
	int a,b;
	tie(a,b)=trans2(read(S,0,19));
	
	int best=1e9;
	int i,j;
	rep(x,0,sz(grp[a])) rep(y,0,sz(grp[b])){
		if (best>dist(grp[a][x],grp[b][y])){
			best=dist(grp[a][x],grp[b][y]);
			i=x,j=y;
		}
	}
	
	//cout<<a<<" "<<b<<" "<<i<<" "<<j<<endl;
	//cout<<seq[a]<<" "<<seq[b]<<endl;
	
	return write(best,14)+write(i,4)+seq[a]+seq[b];
}

Benjamin

#include "Benjamin.h"

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

#define int long long
#define ii pair<int,int>
#define fi first
#define se second
#define endl '\n'

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound

#define rep(x,s,e) for (int x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e))?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

namespace {

int read(string s,int i,int j){
	int res=0;
	rep(x,i,j+1){
		res<<=1;
		if (s[x]=='1') res++;
	}
	
	return res;
}

string write(int i,int j){
	string s="";
	
	rep(x,0,j){
		s+='0'+(i&1);
		i>>=1;
	}
	
	reverse(all(s));
	return s;
}

int trans1(int i,int j){
	int IDX=0;
	rep(y,0,10005){
		rep(x,0,y+1){
			if (x==i && y==j) return IDX;
			IDX++;
		}
	}
	
	return -1;
}

const int BUC=7;
const int BS=2*BUC-1;

int a,b;

vector<int> al[20];

int dfs(int i,int p,int j){
	if (i==j) return 0;
	
	for (auto it:al[i]){
		if (it==p) continue;
		int temp=dfs(it,i,j);
		if (temp!=-1) return temp+1;
	}
	return -1;
}

int calc(int i,int j,string s){
	rep(x,0,20) al[x].clear();
	
	int num=0;
	for (auto it:s) if (it=='1') num++;
	while (sz(s)>2*num) s.pob();
	
	//cout<<s<<endl;
	//cout<<i<<" "<<j<<endl;
	
	vector<int> stk={0};
	int IDX=1;
	
	for (auto it:s){
		if (it=='0'){
			al[stk.back()].pub(IDX);
			al[IDX].pub(stk.back());
			
			stk.pub(IDX);
			IDX++;
		}
		else{
			stk.pob();
		}
	}
	
	return dfs(i,-1,j);
}

}

string SendB(signed N, signed X, signed Y) {
	a=X,b=Y;
	if (a>b) swap(a,b);
	return write(trans1(a/BS,b/BS),20);
}

signed Answer(string T) {
	a%=BS,b%=BS;
	
	int dist=read(T,0,13);
	int r1=read(T,14,17),r2=0;
	
	if (dist==0){
		return calc(a%BS,b%BS,T.substr(18,24));
	}
	else{
		return dist+calc(r1,a%BS,T.substr(18,24))+calc(r2,b%BS,T.substr(42,24));
	}
}

Compilation message (stderr)

Ali.cpp: In function 'std::string SendA(std::string)':
Ali.cpp:177:8: warning: variable 'j' set but not used [-Wunused-but-set-variable]
  177 |  int i,j;
      |        ^
Ali.cpp:188:33: warning: 'i' may be used uninitialized in this function [-Wmaybe-uninitialized]
  188 |  return write(best,14)+write(i,4)+seq[a]+seq[b];
      |                                 ^
grader_ali.cpp:10:8: warning: '{anonymous}::_randmem' defined but not used [-Wunused-variable]
   10 |   char _randmem[12379];
      |        ^~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 54 / 85