oj.uz

답안 #885829

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
885829 2023-12-10T20:26:49 Z jamjanek Flights (JOI22_flights) C++17
95 / 100
 351 ms 6712 KB 
#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;
}

#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

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.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 1432 KB Output is correct
2 Correct 0 ms 1432 KB Output is correct
3 Correct 0 ms 1684 KB Output is correct
4 Correct 0 ms 1432 KB Output is correct
5 Correct 1 ms 1432 KB Output is correct
6 Correct 10 ms 4756 KB Output is correct
7 Correct 10 ms 4928 KB Output is correct
8 Correct 10 ms 4720 KB Output is correct
9 Correct 10 ms 4772 KB Output is correct
10 Correct 10 ms 5000 KB Output is correct
11 Correct 9 ms 4304 KB Output is correct
12 Correct 7 ms 3960 KB Output is correct
13 Correct 8 ms 3956 KB Output is correct
14 Correct 9 ms 4800 KB Output is correct
15 Correct 9 ms 5512 KB Output is correct
16 Correct 7 ms 3800 KB Output is correct

Subtask #2
80.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1524 KB Output is correct
2 Partially correct 73 ms 5824 KB Output is partially correct
3 Correct 3 ms 1536 KB Output is correct
4 Correct 344 ms 5716 KB Output is correct
5 Correct 351 ms 5340 KB Output is correct
6 Correct 342 ms 5364 KB Output is correct
7 Partially correct 319 ms 6120 KB Output is partially correct
8 Correct 335 ms 5628 KB Output is correct
9 Partially correct 285 ms 6244 KB Output is partially correct
10 Partially correct 279 ms 6028 KB Output is partially correct
11 Correct 316 ms 5364 KB Output is correct
12 Correct 43 ms 4480 KB Output is correct
13 Correct 183 ms 5208 KB Output is correct
14 Correct 189 ms 5516 KB Output is correct
15 Correct 4 ms 1600 KB Output is correct
16 Partially correct 299 ms 6712 KB Output is partially correct
17 Partially correct 286 ms 6476 KB Output is partially correct
18 Partially correct 290 ms 6232 KB Output is partially correct
19 Partially correct 294 ms 5992 KB Output is partially correct
20 Partially correct 193 ms 6112 KB Output is partially correct
21 Partially correct 293 ms 6372 KB Output is partially correct
22 Correct 223 ms 4732 KB Output is correct
23 Correct 221 ms 4752 KB Output is correct
24 Correct 226 ms 4680 KB Output is correct
25 Partially correct 223 ms 4888 KB Output is partially correct
26 Correct 236 ms 4908 KB Output is correct
27 Correct 231 ms 4996 KB Output is correct
28 Correct 223 ms 4800 KB Output is correct
29 Correct 215 ms 4432 KB Output is correct
30 Correct 219 ms 4760 KB Output is correct
31 Correct 219 ms 4868 KB Output is correct
32 Correct 216 ms 4688 KB Output is correct
33 Correct 214 ms 4056 KB Output is correct
34 Correct 227 ms 4756 KB Output is correct
35 Partially correct 222 ms 4468 KB Output is partially correct
36 Correct 222 ms 4704 KB Output is correct
37 Correct 220 ms 4696 KB Output is correct
38 Correct 219 ms 4584 KB Output is correct
39 Correct 38 ms 4384 KB Output is correct
40 Partially correct 320 ms 5800 KB Output is partially correct