Submission #885713

#	Time	Username	Problem	Language	Result	Execution time	Memory
885713		jamjanek	Flights (JOI22_flights)	C++17	59 / 100	220 ms	4328 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;
        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);
        }
         
        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++)
        		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;
        	//printf("odczytalam : u = %d, v = %d\n", u, v);
        	if(u==v){
        		dfs3(legenda[u*2*B], -1);
        		return drzewko;
        	}
        	najblizej[0]=1000000;
        	dfs4(legenda[u*2*B], -1, v, 0);
        	int pv=-2137, pu=legenda[u*2*B];
        	for(i=0;i<n;i++)
        		if(odleglosci[i][0]==najblizej[0] && id[i]/(2*B)==v){
        			pv = i;
        			break;
        		}
        	najblizej[1]=1000000;
        	dfs4(pv, -1, u, 1);
     
        	string out;
        	for(i=0;i<14;i++)
        		out+='0'+((najblizej[0]>>i)&1);
        	for(i=0;i<13;i++){
        		if(legenda[u*2*B+i]==-1)
        			out+="0000";
        		else{
        			int pom = odleglosci[legenda[u*2*B+i]][1]-najblizej[1];
        			for(int j=0;j<4;j++)
        				out+='0'+((pom>>j)&1);
        		}
        	}
        	for(i=0;i<13;i++){
        		if(legenda[v*2*B+i]==-1)
        			out+="0000";
        		else{
        			int pom = odleglosci[legenda[v*2*B+i]][0]-najblizej[0];
        			for(int j=0;j<4;j++)
        				out+='0'+((pom>>j)&1);
        		}
        	}
        	//for(i=0;i<28;i++)
        	//	printf("Legenda[%d] = %d\n", i, legenda[i]);
        	//printf("pv = %d pu = %d\n", pv, pu);
        	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();
		}
		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);
	pom = 0;
	for(i=0;i<4;i++){
		if(T[14+y%(2*B)*4+i]=='1')
			pom+=(1<<i);
	}
	wynik+=pom;
	//printf("odlegloc w u = %d\n", pom);
	pom = 0;
	for(i=0;i<4;i++){
		if(T[14+13*4+x%(2*B)*4+i]=='1')
			pom+=(1<<i);
	}
	wynik+=pom;
	//printf("odlegloc w v = %d\n", pom);
	//printf("odlegloc = %d\n", wynik);
	//cout<<T<<"\n";
	return wynik;
}

Compilation message (stderr)

Ali.cpp: In function 'std::string SendA(std::string)':
Ali.cpp:123:24: warning: unused variable 'pu' [-Wunused-variable]
  123 |          int pv=-2137, pu=legenda[u*2*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: 44 / 85