| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 885498 | jamjanek | Flights (JOI22_flights) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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=-2137;
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);
for(i=0;i<n;i++)
if(odleglosci[i][1]==najblizej[1] && id[i]/(2*B)==u){
pu = i;
break;
}
najblizej[2] = 1000000;
dfs4(pu, -1, v, 2);
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]][2]-najblizej[2];
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;
}
#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=-2137;
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);
for(i=0;i<n;i++)
if(odleglosci[i][1]==najblizej[1] && id[i]/(2*B)==u){
pu = i;
break;
}
najblizej[2] = 1000000;
dfs4(pu, -1, v, 2);
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]][2]-najblizej[2];
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;
}