Submission #861111

#	Time	Username	Problem	Language	Result	Execution time	Memory
861111		willychan	Flights (JOI22_flights)	C++17	15 / 100	39 ms	2968 KiB

Ali

#include "Ali.h"
#include<iostream>
#include <string>
#include <vector>
#include<cassert>
#include<queue>
namespace {
std::vector<std::vector<int> > side;
int rN = 0;
std::vector<int> p[20];
std::vector<int> dep;
void dfs(int cur){
	for(int i : side[cur])	{
		if(!dep[i]){
			p[0][i]= cur;
			dep[i]=dep[cur]+1;
			dfs(i);
		}
	}
}
int dis2(int a,int b){
	if(a==b) return 0;
	if(dep[a]>dep[b]) std::swap(a,b);
	int oga = a;
	int ogb = b;
	for(int i=19;i>=0;i--){
		if(dep[p[i][b]]>dep[a]) b=p[i][b];
	}
	b = p[0][b];
	if(a==b) return dep[ogb]-dep[oga];
	for(int i=19;i>=0;i--){
		if(p[i][a]!=p[i][b]){
			a = p[i][a];
			b = p[i][b];
		}
	}
	b = p[0][b];
	a = p[0][a];
	int c = b;
	assert(a==b);
	return dep[oga]-dep[c]+dep[ogb]-dep[c];
}
int dis(int a,int b){
	std::vector<int> ans(rN,1e9);
	ans[a]=0;
	std::queue<int> q;
	q.push(a);
	while(q.size()){
		int cur = q.front();
		q.pop();
		for(auto i : side[cur]){
			if(ans[i]>ans[cur]+1){
				ans[i]=ans[cur]+1;
				q.push(i);
			}
		}
	}
	return ans[b];
}
std::string dtb(int x){
	std::string s;
	for(int i=0;i<14;i++){
		if((x>>i)&1) s+='1';
		else s+='0';
	}
	return s;
}

}

void Init(int N, std::vector<int> U, std::vector<int> V) {
	rN=N;
	side.resize(N);
	dep.resize(N);
	for(int i=0;i<20;i++) p[i].resize(N);
	for(int i=0;i<N;i++){
		dep[i]=0;
		side[i].clear();
		for(int k=0;k<20;k++) p[k][i]=0;
	}
	for(int i=0;i<N-1;i++){
		side[U[i]].push_back(V[i]);
		side[V[i]].push_back(U[i]);
	}
	dep[0]=1;
	dfs(0);
	for(int j=1;j<20;j++)	{
		for(int i=1;i<N;i++) p[j][i] = p[j-1][p[j-1][i]];
	}
	for(int i=0;i<N;i++) SetID(i,i);
}

std::string SendA(std::string S) {
	std::string re;
	int a = 0;
	int b = 0;
	for(int i=0;i<6;i++){
		if(S[i]=='1'){
			if(S[14+i]=='1') a+=(1<<i);
			else b+=(1<<i);
		}else{
			if(S[14+i]=='1') {a+=(1<<i);b+=(1<<i);}
		}
	}

	for(int k=0;k<(1<<8);k++){
		int aa = a;
		int bb = b;
		for(int i=6;i<14;i++){
			if(S[i]=='1'){
				if((k>>(i-6))&1) aa+=(1<<i);
				else bb+=(1<<i);
			}else{
				if((k>>(i-6))&1) {aa+=(1<<i);bb+=(1<<i);}
			}
		}
		if(aa>=rN || bb>=rN) re+=dtb(0);
		else {re+=dtb(dis(aa,bb)); 
//			std::cout<<"\n"<<aa<<" "<<bb<<" "<<dis(aa,bb)<<"\n";
		}
	}
	return re;
}

Benjamin

#include "Benjamin.h"
#include <string>
#include <vector>

namespace {
int x;
int y;
int variable_example = 0;

}

std::string SendB(int N, int X, int Y) {
	x= X;
	y = Y;
	std::string s;
	int b = X^Y;
	for(int i=0;i<14;i++){
		if((b>>i)&1) s.push_back('1');
		else s.push_back('0');
	}
	for(int i=0;i<6;i++){
		if((X>>i)&1) s.push_back('1');
		else s.push_back('0');
	}
	return s;
}

int Answer(std::string T) {
  int g=0;
  for(int i=6;i<14;i++){
  	if((x>>i)&1) g+=(1<<(i-6));
  }
  int ans = 0;
  for(int i=0;i<14;i++){
  	 if(T[14*(g)+i]=='1') ans+=(1<<i);
  }
  return ans;
}

Compilation message (stderr)

Ali.cpp:21:5: warning: 'int {anonymous}::dis2(int, int)' defined but not used [-Wunused-function]
   21 | int dis2(int a,int b){
      |     ^~~~
grader_ali.cpp:10:8: warning: '{anonymous}::_randmem' defined but not used [-Wunused-variable]
   10 |   char _randmem[12379];
      |        ^~~~~~~~

Benjamin.cpp:8:5: warning: '{anonymous}::variable_example' defined but not used [-Wunused-variable]
    8 | int variable_example = 0;
      |     ^~~~~~~~~~~~~~~~

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