Submission #885829

#	Time	Username	Problem	Language	Result	Execution time	Memory
885829		jamjanek	Flights (JOI22_flights)	C++17	95 / 100	351 ms	6712 KiB

Ali

#include "Ali.h"
#include <string>
#include <vector>
#include<bits/stdc++.h>
using namespace std;
string drzewkaA[66] = {"000000111111000000111111","000000111111000001011111","000000111111000001101111","000000111111000001110111","000000111111000001111011","000000111111000010110111","000000111111000010111011","000000111111000011001111","000000111111000011011011","000000111111000011100111","000000111111000101100111","000001011111000001011111","000001011111000001101111","000001011111000001110111","000001011111000001111011","000001011111000010110111","000001011111000010111011","000001011111000011001111","000001011111000011011011","000001011111000011100111","000001011111000101100111","000001101111000001101111","000001101111000001110111","000001101111000001111011","000001101111000010110111","000001101111000010111011","000001101111000011001111","000001101111000011011011","000001101111000011100111","000001101111000101100111","000001110111000001110111","000001110111000001111011","000001110111000010110111","000001110111000010111011","000001110111000011001111","000001110111000011011011","000001110111000011100111","000001110111000101100111","000001111011000001111011","000001111011000010110111","000001111011000010111011","000001111011000011001111","000001111011000011011011","000001111011000011100111","000001111011000101100111","000010110111000010110111","000010110111000010111011","000010110111000011001111","000010110111000011011011","000010110111000011100111","000010110111000101100111","000010111011000010111011","000010111011000011001111","000010111011000011011011","000010111011000011100111","000010111011000101100111","000011001111000011001111","000011001111000011011011","000011001111000011100111","000011001111000101100111","000011011011000011011011","000011011011000011100111","000011011011000101100111","000011100111000011100111","000011100111000101100111","000101100111000101100111",};

const int B = 7;

vector<int> graf1[10010], graf2[10010];
int preorder[10010]; int preit;
int legenda[30010];
int bijekcja[10010];
int nr2;
int id[10010];
int r[10010];
bool odw[10010];
void dfs1(int x, int o){
	preorder[preit++] = x;
	r[x]=1;
	for(auto j: graf1[x])
		if(j!=o)
			dfs1(j, x);
	if(r[x]<B){
		if(o!=-1){
			r[o]+=r[x];
			graf2[o].push_back(x);
			graf2[x].push_back(o);
		}
	}
}

struct grupa{
	int drzewkoid;
	vector<int>numery;
	
	vector<int>graf[14];
	string napisypoddrzew[14];
	int r[14];
	int wolny;
	int preorder[14];
	int preit=0;
};
vector<grupa>grupy;
int dfsG1(int x, int o, int ile, grupa &G){
	if(o==0){
		if(x<(int)G.numery.size())
			ile = min(ile, B-1-r[G.numery[x]]);
		else
			ile = min(ile, B-2);
	}
	//printf("%d %d\n", x, ile);
	int zrobione = 0;
	if(zrobione>=ile)return 0;
	while(zrobione<ile && ((G.graf[x].size()<3 && o!=-1) || G.graf[x].size()<2))
	{
		G.graf[x].push_back(G.wolny);
		G.graf[G.wolny++].push_back(x);
		zrobione++;
	}
	if(zrobione>=ile)return zrobione;
	for(auto j: G.graf[x])
		if(j!=o)
			zrobione+=dfsG1(j, x, ile-zrobione, G);
	return zrobione;
}
bool cmp(int x, int y){
//	cout<<"\""<<grupy[nr2].napisypoddrzew[x]<<"\"   \""<<grupy[nr2].napisypoddrzew[y]<<"\" "<< (grupy[nr2].napisypoddrzew[x]<grupy[nr2].napisypoddrzew[y])<<"\n";
	return ("0"+grupy[nr2].napisypoddrzew[x]+"1")<("0"+grupy[nr2].napisypoddrzew[y]+"1");
}
void dfsG2(int x, int o, grupa &G){
	for(auto j: G.graf[x])
		if(j!=o){
			dfsG2(j, x, G);
		}
	for(int i=0;i<(int)G.graf[x].size();i++)
		if(G.graf[x][i]==o){
			swap(G.graf[x][i], G.graf[x].back());
			G.graf[x].pop_back();
			break;
		}
	sort(G.graf[x].begin(), G.graf[x].end(), cmp);
	for(auto j: G.graf[x])
		G.napisypoddrzew[x]+="0"+G.napisypoddrzew[j]+"1";
}
void dfsG3(int x, grupa &G){
	//printf("%d %d\n", x, G.preit);
	G.preorder[x] = G.preit++;
	for(auto j: G.graf[x])
		dfsG3(j, G);
}
void konfiguruj(int ng){
	nr2 = ng;
	auto &G = grupy[ng];
	G.wolny = G.numery.size();
	int i;
	for(i=0;i<(int)G.numery.size();i++)
		bijekcja[G.numery[i]] = i;
	for(auto j: G.numery)
		for(auto k: graf2[j])
			G.graf[bijekcja[j]].push_back(bijekcja[k]);
	int dopelnij = 2*B-1-r[G.numery[0]];
	/*
	printf("Grupa nr %d\n", ng);
	for(i=0;i<13;i++){
		printf("%d: ", i);
		for(auto j: G.graf[i])
			printf("%d ", j);
		printf("\n");
	}*/
	dfsG1(0, -1, dopelnij, G);
	/*
	printf("Do dopelnienia %d, Po dopelnieniu Grupa nr %d\n", dopelnij, ng);
	for(i=0;i<13;i++){
		printf("%d: ", i);
		for(auto j: G.graf[i])
			printf("%d ", j);
		printf("\n");
	}*/
	dfsG2(0, -1, G);
	// jeszcze trzeba stworzyc legende
	dfsG3(0, G);
	/*
	printf("Ostatecznie Grupa nr %d\n", ng);
	for(i=0;i<13;i++){
		printf("%d: ", i);
		for(auto j: G.graf[i])
			printf("%d ", j);
		printf("\n");
	}*/
//	printf("Ppreorder: ");for(i=0;i<13;i++)printf("%d ", G.preorder[i]);printf("\n");
	for(i=0;i<(int)G.numery.size();i++){
//		printf("id[%d] = %d    %d\n", G.numery[i], ng*2*B+G.preorder[i], preorder[i]);
		id[G.numery[i]] = ng*2*B+G.preorder[i];
		legenda[ng*2*B+G.preorder[i]] = G.numery[i];
	}
//	cout<<G.napisypoddrzew[0]<<"\n";
	for(i=0;i<66;i++)
		if(G.napisypoddrzew[0]==drzewkaA[i])break;
//	printf("%d\n", i);
	G.drzewkoid = i;
	
}

void dfs2(int x, int o){
	odw[x] = 1;
	grupy.back().numery.push_back(x);
	for(auto j: graf2[x])
		if(j!=o)
			dfs2(j, x);
}
string drzewko;
void dfs3(int x, int o){
	for(auto j: graf2[x])
		if(j!=o){
			drzewko+='0';
			dfs3(j,x);
			drzewko+='1';
		}
			
}

int odleglosci[30010][3];
int najblizej[3];
int n;
void dfs4(int x, int o, int szukany, int nro){
	if(o==-1)
		odleglosci[x][nro] = 0;
	else
		odleglosci[x][nro] = odleglosci[o][nro]+1;
	if(id[x]/(2*B)==szukany)
		najblizej[nro] = min(najblizej[nro], odleglosci[x][nro]);
	for(auto j: graf1[x])
		if(j!=o)
			dfs4(j, x, szukany, nro);
}

int korzen;
void Init(int N, std::vector<int> U, std::vector<int> V) {
	grupy.clear();
	int i;
	n = N;
	for(i=0;i<3*N;i++){
		legenda[i] = -1;
		odleglosci[i][0] = 0;
		odleglosci[i][1] = 0;
		odleglosci[i][2] = 0;
	}
	drzewko.clear();
	preit = 0;
	nr2 = 0;
	for(i=0;i<n;i++){
		graf1[i].clear();
		graf2[i].clear();
		odw[i] = 0;
		preorder[i] = 0;
		id[i] = 0;
		r[i] = 0;
	}
	for(i=0;i<N-1;i++){
		graf1[U[i]].push_back(V[i]);
		graf1[V[i]].push_back(U[i]);
	}
	for(i=0;i<n;i++)
		if(graf1[i].size()<=2)break;
	korzen = i;
	dfs1(korzen,-1);
	for(i=0;i<N;i++)
		if(!odw[preorder[i]]){
			nr2 = 0;
			grupy.push_back({});
			dfs2(preorder[i], -1);
		}
	for(i=0;i<(int)grupy.size();i++)
		konfiguruj(i);
	for(i=0;i<N;i++)
		SetID(i, id[i]);
}



std::string SendA(std::string S) {
	//cout<<"otzyamalam string: "<<S<<"\n";
	int liczba = 0, i;
	for(i=0;i<20;i++)
		if(S[i]=='1')
			liczba+=(1<<i);
	int u = 0, v;
	int suma = 0;
	for(i=1;;i++){
		if(suma+i<=liczba)
			suma+=i;
		else
			break;
	}
	u = i-1;
	v = liczba-suma;
	//u>=v
//	printf("odczytalam : u = %d, v = %d\n", u, v);
	if(u==v){
		int pom = grupy[u].drzewkoid;
		string out;
		for(i=0;i<7;i++)
			out+='0'+((pom>>i)&1);
		return out;
	}
	
//	for(i=0;i<14*grupy.size();i++)
//		printf("%d: id = %d\n", i, id[i]);
	
	najblizej[0]=1000000;
	dfs4(legenda[u*2*B], -1, v, 0);
	int pv=-2137;
	for(i=0;i<n;i++)
		if(odleglosci[i][0]==najblizej[0] && id[i]/(2*B)==v){
			pv = i;
			break;
		}
//	printf("pv = %d\n", pv);
	string out;
/*
	for(i=0;i<14;i++)
		out+='0'+((najblizej[0]>>i)&1);
	for(i=0;i<4;i++)
		out+='0'+(((id[pv]%(2*B))>>i)&1);

	//dodaj drzewko v 
	for(i=0;i<7;i++)
		out+='0'+((grupy[v].drzewkoid>>i)&1);
	//dodaj drzewko u 
	for(i=0;i<7;i++)
		out+='0'+((grupy[u].drzewkoid>>i)&1);
//	cout<<najblizej[0]<<"  "<<out<<"\n";
*/
	//najblizej[0] od 0 do 10000 ?
	//id[pv]%(2*B) od 0 do 12 ?
	//grupy[v].drzewkoid od 0 do 65
	//grupy[u].drzewkoid od 0 do 65
	long long res = 0;
	res+=najblizej[0];
	res*=13;
	res+=id[pv]%(2*B);
	res*=66;
	res+=grupy[v].drzewkoid;
	res*=66;
	res+=grupy[u].drzewkoid;
//	printf("%d %d %d %d\n", najblizej[0], id[pv]%(2*B), grupy[v].drzewkoid, grupy[u].drzewkoid);

	for(i=0;;i++){
		if(res<=(1<<i)){
			for(int j=0;j<i;j++)
			out+='0'+((res>>j) &1);
			return out;
		}
		res-=1<<i;
	}
	return out;
}

Benjamin

#include "Benjamin.h"
#include <string>
#include <vector>
#include<bits/stdc++.h>
using namespace std;
string drzewkaB[66] = {"000000111111000000111111","000000111111000001011111","000000111111000001101111","000000111111000001110111","000000111111000001111011","000000111111000010110111","000000111111000010111011","000000111111000011001111","000000111111000011011011","000000111111000011100111","000000111111000101100111","000001011111000001011111","000001011111000001101111","000001011111000001110111","000001011111000001111011","000001011111000010110111","000001011111000010111011","000001011111000011001111","000001011111000011011011","000001011111000011100111","000001011111000101100111","000001101111000001101111","000001101111000001110111","000001101111000001111011","000001101111000010110111","000001101111000010111011","000001101111000011001111","000001101111000011011011","000001101111000011100111","000001101111000101100111","000001110111000001110111","000001110111000001111011","000001110111000010110111","000001110111000010111011","000001110111000011001111","000001110111000011011011","000001110111000011100111","000001110111000101100111","000001111011000001111011","000001111011000010110111","000001111011000010111011","000001111011000011001111","000001111011000011011011","000001111011000011100111","000001111011000101100111","000010110111000010110111","000010110111000010111011","000010110111000011001111","000010110111000011011011","000010110111000011100111","000010110111000101100111","000010111011000010111011","000010111011000011001111","000010111011000011011011","000010111011000011100111","000010111011000101100111","000011001111000011001111","000011001111000011011011","000011001111000011100111","000011001111000101100111","000011011011000011011011","000011011011000011100111","000011011011000101100111","000011100111000011100111","000011100111000101100111","000101100111000101100111",};

const int B = 7;
int x,y;
std::string SendB(int N, int X, int Y) {
	//printf("Benjamin: X=%d Y=%d\n", X, Y);
	int i;
	if(X>Y)swap(X,Y);//X<Y
	x = X;
	y = Y;
	int u, v;
	v = X/(2*B);
	u = Y/(2*B);
	int suma=0;
	for(i=0;i<=u;i++)
		suma+=i;
	suma+=v;
	string out;
	for(i=0;i<20;i++)
		out+='0'+((suma>>i)&1);
	//cout<<out;exit(0);
	return out;
}

vector<int>graf[20];
int odl[20];
void dfs(int x, int o){
	if(o>-1)
		odl[x] = odl[o]+1;
	for(auto j: graf[x])
		if(j!=o)
			dfs(j, x);
}
int Answer(std::string T) {
	//cout<<T<<"\n";
	int u, v, i;
	for(i=0;i<20;i++){
		graf[i].clear();
		odl[i] = 0;
	}
	v = x/(2*B);
	u = y/(2*B);
	if(u==v){
		int pom = 0;
		for(i=0;i<7;i++)
			if(T[0+i]=='1')
				pom+=1<<i;
		T = drzewkaB[pom];
		stack<int>stos;
		stos.push(0);
		int it=1;
		for(auto j:T){
			if(j=='0'){//dodaj
				graf[stos.top()].push_back(it);
				graf[it].push_back(stos.top());
				stos.push(it++);
			}
			else
				stos.pop();
		}
		odl[x%(2*B)]=0;
		dfs(x%(2*B), -1);
		return odl[y%(2*B)];
	}
	int wynik = 0;
	int pom=0;
	long long res = 0;
	for(i=0;i<(int)T.size();i++)
		res+=1<<i;
	for(i=0;i<(int)T.size();i++)
		if(T[i]=='1')
			res+=1<<i;
	
	int ur = res%66;
	res/=66;
	int vr = res%66;
	res/=66;
	int pv = res%13;
	res/=13;
	int odleglosc = res;
//	printf("%d %d %d %d", odleglosc, pv, vr, ur);
	wynik = odleglosc;
	//printf("odlegloc miedzy grupami= %d\n", pom);
	//printf("pv = %d\n", pv);
	
	stack<int>stos;
	string drzewko = drzewkaB[vr];
	stos.push(0);
	int it=1;
	for(auto j:drzewko){
		if(j=='0'){//dodaj
			graf[stos.top()].push_back(it);
			graf[it].push_back(stos.top());
			stos.push(it++);
		}
		else
			stos.pop();
		if(stos.size()==0)break;
	}
	odl[pv] = 0;
	dfs(pv, -1);
	wynik += odl[x%(2*B)];
	//printf("odleglosc w v = %d\n", odl[x%(2*B)]);
	
	
	drzewko= drzewkaB[ur];
	while(stos.size())stos.pop();
	stos.push(0);
	for(i=0;i<20;i++){
		graf[i].clear();
		odl[i] = 0;
	}
	it=1;
	for(auto j:drzewko){
		if(j=='0'){//dodaj
			graf[stos.top()].push_back(it);
			graf[it].push_back(stos.top());
			stos.push(it++);
		}
		else
			stos.pop();
		if(stos.size()==0)break;
	}
	odl[0] = 0;
	dfs(0, -1);
	wynik += odl[y%(2*B)];
	//printf("odleglosc w u = %d, y = %d\n", odl[y%(2*B)], y%(2*B));
	return wynik;
}
//10000000000000 1100 0100001 0100001

Compilation message (stderr)

grader_ali.cpp:10:8: warning: '{anonymous}::_randmem' defined but not used [-Wunused-variable]
   10 |   char _randmem[12379];
      |        ^~~~~~~~

Benjamin.cpp: In function 'int Answer(std::string)':
Benjamin.cpp:71:6: warning: unused variable 'pom' [-Wunused-variable]
   71 |  int pom=0;
      |      ^~~

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