Submission #885745

#	Time	Username	Problem	Language	Result	Execution time	Memory
885745		jamjanek	Flights (JOI22_flights)	C++17	15 / 100	45 ms	3948 KiB

Ali

#include "Ali.h"
#include <string>
#include <vector>
#include<bits/stdc++.h>
using namespace std;
const int B = 7;
const int C = 1429;

vector<int> graf1[10010], graf2[10010];
int preorder[10010]; int preit;
int legenda[30010];
int nr=0, nr2=0;
int id[10010];
int r[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);
		}
	}
}
bool odw[10010];
void dfs2(int x){
	id[x] = nr*2*B+nr2++;
	legenda[id[x]] = x;
	odw[x] = 1;
	for(auto j: graf2[x])
		if(!odw[j])
			dfs2(j);
}
string drzewko;
int zlicz=0;
void dfs3(int x, int o){
	//cout<<drzewko<<"\n";
	//zlicz++;
	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);
}

void Init(int N, std::vector<int> U, std::vector<int> V) {
	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;
	nr = 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]);
	}
	dfs1(0,-1);
	for(i=0;i<N;i++)
		if(!odw[preorder[i]]){
			nr2=0;
			dfs2(preorder[i]);
			nr++;
		}
	/*
	for(i=0;i<N;i++){
		printf("%d: r=%d id=%d\n", i, r[i], id[i]);
	}*/
	for(i=0;i<N;i++)
		SetID(i, id[i]);
}


int dfs5(int x, int o){
	int w = 1;
	for(auto j: graf2[x])
		if(j!=o)
			w+=dfs5(j,x);
	return w;
}

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){
		//zlicz = 0;
		drzewko="";
		dfs3(legenda[u*2*B], -1);
		//cout<<drzewko<<"\n"<<zlicz<<"\n";
		return drzewko;
	}

	najblizej[0]=1000000;
	dfs4(legenda[u*2*B], -1, v, 0);
	int pv=-2137, pu=-2137;
	for(i=0;i<n;i++)
		if(odleglosci[i][0]==najblizej[0] && id[i]/(2*B)==v){
			pv = i;
			break;
		}
	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);
	drzewko="";
	//dodaj drzewko v 
	dfs3(legenda[v*2*B], -1);
	if(dfs5(legenda[v*2*B], -1)>13){
		printf("ZA DUZA GRUPA");
		exit(0);
	}
	while(drzewko.size()<24)drzewko+='1';
	/*
	if(drzewko.size()>32){
		printf("ZA DUZE DRZEWKO");
		exit(0);
	}*/
	for(i=0;i<24;i++)
		out+=drzewko[i];
//	out=out+drzewko;
	drzewko="";
	//dodaj drzewko u 
	dfs3(legenda[u*2*B], -1);
	if(dfs5(legenda[u*2*B], -1)>13){
		printf("ZA DUZA GRUPA");
		exit(0);
	}
	while(drzewko.size()<24)drzewko+='1';
	/*
	if(drzewko.size()>32){
		printf("ZA DUZE DRZEWKO");
		exit(0);
	}*/
	for(i=0;i<24;i++)
		out+=drzewko[i];
	//out+=drzewko;
	return out;
}

Benjamin

#include "Benjamin.h"
#include <string>
#include <vector>
#include<bits/stdc++.h>
using namespace std;
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) {
	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){
		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;
	for(i=0;i<14;i++)
		if(T[i]=='1')
			pom+=(1<<i);
	wynik = pom;
	//printf("odlegloc miedzy grupami= %d\n", pom);
	int pv = 0;
	for(i=0;i<4;i++)
		if(T[i+14]=='1')
			pv+=1<<i;
	//printf("pv = %d\n", pv);
	stack<int>stos;
	string drzewko = T.substr(14+4, 24);
	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= T.substr(14+4+24, 24);
	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));
	//cout<<drzewko<<"\n";
	//cout<<T<<"\n";
	//cout<<T.substr(14+4+24, 24)<<"\n";
	return wynik;
}
//10000000000000 0100 001111111111111111111111 000000111111111111111111

Compilation message (stderr)

Ali.cpp: In function 'std::string SendA(std::string)':
Ali.cpp:144:16: warning: unused variable 'pu' [-Wunused-variable]
  144 |  int pv=-2137, pu=-2137;
      |                ^~
grader_ali.cpp:10:8: warning: '{anonymous}::_randmem' defined but not used [-Wunused-variable]
   10 |   char _randmem[12379];
      |        ^~~~~~~~

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