Submission #885712

#	Time	Username	Problem	Language	Result	Execution time	Memory
885712		jamjanek	Flights (JOI22_flights)	C++17	0 / 100	9 ms	2208 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[2]>>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:20: 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: 0 / 15
• Subtask 2: 0 / 85