oj.uz

Submission #567921

# Submission time Handle Problem Language Result Execution time Memory
567921 2022-05-24T11:06:17 Z errorgorn Flights (JOI22_flights) C++17
71 / 100
 467 ms 5364 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,14)+write(i,4)+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 dist=read(T,0,13);
	int r1=read(T,14,17),r2=0;
	
	if (dist==0){
		return calc(a%BS,b%BS,T.substr(18,22));
	}
	else{
		return dist+calc(r1,a%BS,T.substr(18,22))+calc(r2,b%BS,T.substr(40,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:33: warning: 'i' may be used uninitialized in this function [-Wmaybe-uninitialized]
  189 |  return write(best,14)+write(i,4)+seq[a]+seq[b];
      |                                 ^
grader_ali.cpp:10:8: warning: '{anonymous}::_randmem' defined but not used [-Wunused-variable]
   10 |   char _randmem[12379];
      |        ^~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1424 KB Output is correct
2 Correct 1 ms 1424 KB Output is correct
3 Correct 2 ms 1424 KB Output is correct
4 Correct 2 ms 1424 KB Output is correct
5 Correct 1 ms 1424 KB Output is correct
6 Correct 9 ms 2828 KB Output is correct
7 Correct 9 ms 2824 KB Output is correct
8 Correct 13 ms 2912 KB Output is correct
9 Correct 9 ms 2768 KB Output is correct
10 Correct 16 ms 3304 KB Output is correct
11 Correct 9 ms 2608 KB Output is correct
12 Correct 9 ms 2828 KB Output is correct
13 Correct 9 ms 2916 KB Output is correct
14 Correct 8 ms 2956 KB Output is correct
15 Correct 11 ms 4408 KB Output is correct
16 Correct 9 ms 3088 KB Output is correct

Subtask #2
56.0 / 85.0

# Verdict Execution time Memory Grader output
1 Partially correct 2 ms 1424 KB Output is partially correct
2 Partially correct 74 ms 5112 KB Output is partially correct
3 Partially correct 9 ms 1520 KB Output is partially correct
4 Partially correct 346 ms 3940 KB Output is partially correct
5 Partially correct 338 ms 3972 KB Output is partially correct
6 Partially correct 345 ms 4068 KB Output is partially correct
7 Partially correct 403 ms 5364 KB Output is partially correct
8 Partially correct 389 ms 3984 KB Output is partially correct
9 Partially correct 355 ms 4324 KB Output is partially correct
10 Partially correct 327 ms 4984 KB Output is partially correct
11 Partially correct 358 ms 3780 KB Output is partially correct
12 Partially correct 49 ms 2968 KB Output is partially correct
13 Partially correct 244 ms 3900 KB Output is partially correct
14 Partially correct 225 ms 4040 KB Output is partially correct
15 Partially correct 11 ms 1644 KB Output is partially correct
16 Partially correct 409 ms 4468 KB Output is partially correct
17 Partially correct 369 ms 4456 KB Output is partially correct
18 Partially correct 467 ms 4812 KB Output is partially correct
19 Partially correct 400 ms 4916 KB Output is partially correct
20 Partially correct 213 ms 4480 KB Output is partially correct
21 Partially correct 327 ms 5008 KB Output is partially correct
22 Partially correct 376 ms 3356 KB Output is partially correct
23 Partially correct 329 ms 3380 KB Output is partially correct
24 Partially correct 278 ms 3560 KB Output is partially correct
25 Partially correct 291 ms 3436 KB Output is partially correct
26 Partially correct 303 ms 3428 KB Output is partially correct
27 Partially correct 292 ms 3420 KB Output is partially correct
28 Partially correct 291 ms 3444 KB Output is partially correct
29 Partially correct 351 ms 3392 KB Output is partially correct
30 Partially correct 345 ms 3568 KB Output is partially correct
31 Partially correct 289 ms 3568 KB Output is partially correct
32 Partially correct 298 ms 3508 KB Output is partially correct
33 Partially correct 285 ms 3472 KB Output is partially correct
34 Partially correct 328 ms 3388 KB Output is partially correct
35 Partially correct 301 ms 3448 KB Output is partially correct
36 Partially correct 282 ms 3576 KB Output is partially correct
37 Partially correct 285 ms 3444 KB Output is partially correct
38 Partially correct 305 ms 3532 KB Output is partially correct
39 Partially correct 67 ms 3012 KB Output is partially correct
40 Partially correct 463 ms 4640 KB Output is partially correct