oj.uz

Submission #567926

# Submission time Handle Problem Language Result Execution time Memory
567926 2022-05-24T11:10:15 Z errorgorn Flights (JOI22_flights) C++17
0 / 100
 10 ms 2624 KB 
#include "Ali.h"

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ii pair<int,int>
#define fi first
#define se second
#define endl '\n'

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound

#define rep(x,s,e) for (int x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e))?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

namespace {

int read(string s,int i,int j){
	int res=0;
	rep(x,i,j+1){
		res<<=1;
		if (s[x]=='1') res++;
	}
	
	return res;
}

string write(int i,int j){
	string s="";
	
	rep(x,0,j){
		s+='0'+(i&1);
		i>>=1;
	}
	
	reverse(all(s));
	return s;
}

ii trans2(int i){
	int IDX=0;
	rep(y,0,10005){
		rep(x,0,y+1){
			if (IDX==i) return {x,y};
			IDX++;
		}
	}
	
	return {-1,-1};
}

const int BUC=7;
const int BS=2*BUC-1;

int n;
vector<int> al[10005];
int d[10005];
int pp[10005];
vector<int> grp[10005];
vector<vector<int> > v;

void dfs(int i,int p){
	for (auto it:al[i]){
		if (it==p) continue;
		
		d[it]=d[i]+1;
		pp[it]=i;
		dfs(it,i);
		grp[i].insert(grp[i].end(),all(grp[it]));
	}
	
	grp[i].pub(i);
	
	if (sz(grp[i])>=BUC || p==-1){
		v.pub(grp[i]);
		grp[i].clear();
	}
}

int id[10005];
set<int> s;
string seq[10005];

int IDX1,IDX2;

void dfs2(int i,int p){
	id[i]=IDX1*BS+IDX2;
	grp[IDX1].pub(i);
	if (p!=-1) seq[IDX1]+='0';
	IDX2++;
	
	for (auto it:al[i]){
		if (it==p || !s.count(it)) continue;
		dfs2(it,i);
	}
	
	if (p!=-1) seq[IDX1]+='1';
}

int dist(int i,int j){ //damn lazy
	if (d[i]<d[j]) swap(i,j);
	
	int res=0;
	while (i!=j){
		if (d[i]==d[j]){
			res+=2;
			i=pp[i],j=pp[j];
		}
		else{
			res++;
			i=pp[i];
		}
	}
	
	return res;
}

}

void Init(signed N, vector<signed> U, vector<signed> V) {
	rep(x,0,10005) al[x].clear();
	rep(x,0,10005) d[x]=0;
	rep(x,0,10005) pp[x]=-1;
	rep(x,0,10005) grp[x].clear();
	v.clear();
	rep(x,0,10005) id[x]=0;
	rep(x,0,10005) seq[x]="";
	
	n=N;
	rep(x,0,n-1){
		al[U[x]].pub(V[x]);
		al[V[x]].pub(U[x]);
	}
	
	rep(x,0,n) if (sz(al[x])==1){
		//cout<<"debug: "<<x<<endl;
		dfs(x,-1);
		break;
	}
	
	for (auto &it:v) sort(all(it),[](int i,int j){ return d[i]<d[j]; });
	sort(all(v),[](vector<int> i,vector<int> j){
		return d[i[0]]<d[j[0]];
	});
	
	rep(x,0,10005) grp[x].clear();
	
	IDX1=0;
	for (auto it:v){
		s=set<int>(all(it));
		IDX2=0;
		dfs2(it[0],-1);
		
		//for (auto it2:grp[IDX1]) cout<<it2<<" "; cout<<endl;
		//cout<<seq[IDX1]<<endl;
		
		if (!seq[IDX1].empty()) seq[IDX1]=seq[IDX1].substr(1,sz(seq[IDX1])-2);
		while (sz(seq[IDX1])<22) seq[IDX1]+='0';
		IDX1++;
	}
	
	//rep(x,0,n) cout<<id[x]<<" "; cout<<endl;
	rep(x,0,n) SetID(x,id[x]);
}

string SendA(string S) {
	int a,b;
	tie(a,b)=trans2(read(S,0,19));
	
	int best=1e9;
	int i,j;
	rep(x,0,sz(grp[a])) rep(y,0,sz(grp[b])){
		if (best>dist(grp[a][x],grp[b][y])){
			best=dist(grp[a][x],grp[b][y]);
			i=x,j=y;
		}
	}
	
	//cout<<a<<" "<<b<<" "<<i<<" "<<j<<endl;
	//cout<<seq[a]<<" "<<seq[b]<<endl;
	
	return write(best*i+10000,17)+seq[a]+seq[b];
}

#include "Benjamin.h"

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ii pair<int,int>
#define fi first
#define se second
#define endl '\n'

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound

#define rep(x,s,e) for (int x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e))?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

namespace {

int read(string s,int i,int j){
	int res=0;
	rep(x,i,j+1){
		res<<=1;
		if (s[x]=='1') res++;
	}
	
	return res;
}

string write(int i,int j){
	string s="";
	
	rep(x,0,j){
		s+='0'+(i&1);
		i>>=1;
	}
	
	reverse(all(s));
	return s;
}

int trans1(int i,int j){
	int IDX=0;
	rep(y,0,10005){
		rep(x,0,y+1){
			if (x==i && y==j) return IDX;
			IDX++;
		}
	}
	
	return -1;
}

const int BUC=7;
const int BS=2*BUC-1;

int a,b;

vector<int> al[20];

int dfs(int i,int p,int j){
	if (i==j) return 0;
	
	for (auto it:al[i]){
		if (it==p) continue;
		int temp=dfs(it,i,j);
		if (temp!=-1) return temp+1;
	}
	return -1;
}

int calc(int i,int j,string s){
	rep(x,0,20) al[x].clear();
	
	int num=0;
	for (auto it:s) if (it=='1') num++;
	while (sz(s)>2*num) s.pob();
	
	s="0"+s+"1";
	
	//cout<<s<<endl;
	//cout<<i<<" "<<j<<endl;
	
	vector<int> stk={0};
	int IDX=1;
	
	for (auto it:s){
		if (it=='0'){
			al[stk.back()].pub(IDX);
			al[IDX].pub(stk.back());
			
			stk.pub(IDX);
			IDX++;
		}
		else{
			stk.pob();
		}
	}
	
	return dfs(i,-1,j);
}

}

string SendB(signed N, signed X, signed Y) {
	a=X,b=Y;
	if (a>b) swap(a,b);
	return write(trans1(a/BS,b/BS),20);
}

signed Answer(string T) {
	a%=BS,b%=BS;
	
	int temp=read(T,0,16);
	
	int dist=temp%10000;
	int r1=temp/10000,r2=0;
	
	if (dist==0){
		return calc(a%BS,b%BS,T.substr(17,22));
	}
	else{
		return dist+calc(r1,a%BS,T.substr(17,22))+calc(r2,b%BS,T.substr(39,22));
	}
}

Compilation message

Ali.cpp: In function 'std::string SendA(std::string)':
Ali.cpp:178:8: warning: variable 'j' set but not used [-Wunused-but-set-variable]
  178 |  int i,j;
      |        ^
Ali.cpp:189:19: warning: 'i' may be used uninitialized in this function [-Wmaybe-uninitialized]
  189 |  return write(best*i+10000,17)+seq[a]+seq[b];
      |               ~~~~^~
grader_ali.cpp:10:8: warning: '{anonymous}::_randmem' defined but not used [-Wunused-variable]
   10 |   char _randmem[12379];
      |        ^~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1424 KB Output is correct
2 Correct 2 ms 1424 KB Output is correct
3 Correct 1 ms 1512 KB Output is correct
4 Correct 2 ms 1424 KB Output is correct
5 Correct 1 ms 1512 KB Output is correct
6 Incorrect 10 ms 2624 KB Incorrect
7 Halted 0 ms 0 KB -

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 1424 KB Output is partially correct
2 Incorrect 10 ms 2624 KB Incorrect
3 Halted 0 ms 0 KB -