oj.uz

Submission #567901

# Submission time Handle Problem Language Result Execution time Memory
567901 2022-05-24T10:13:34 Z errorgorn Flights (JOI22_flights) C++17
69 / 100
 496 ms 5304 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;
		
		while (sz(seq[IDX1])<2*(BS-1)) 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();
	
	//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,24));
	}
	else{
		return dist+calc(r1,a%BS,T.substr(18,24))+calc(r2,b%BS,T.substr(42,24));
	}
}

Compilation message

Ali.cpp: In function 'std::string SendA(std::string)':
Ali.cpp:177:8: warning: variable 'j' set but not used [-Wunused-but-set-variable]
  177 |  int i,j;
      |        ^
Ali.cpp:188:33: warning: 'i' may be used uninitialized in this function [-Wmaybe-uninitialized]
  188 |  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 1484 KB Output is correct
2 Correct 1 ms 1424 KB Output is correct
3 Correct 1 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 11 ms 2872 KB Output is correct
7 Correct 9 ms 2828 KB Output is correct
8 Correct 11 ms 2844 KB Output is correct
9 Correct 11 ms 2932 KB Output is correct
10 Correct 12 ms 3212 KB Output is correct
11 Correct 9 ms 2564 KB Output is correct
12 Correct 9 ms 2916 KB Output is correct
13 Correct 9 ms 2792 KB Output is correct
14 Correct 10 ms 3040 KB Output is correct
15 Correct 9 ms 4240 KB Output is correct
16 Correct 8 ms 3088 KB Output is correct

Subtask #2
54.0 / 85.0

# Verdict Execution time Memory Grader output
1 Partially correct 2 ms 1424 KB Output is partially correct
2 Partially correct 83 ms 5304 KB Output is partially correct
3 Partially correct 9 ms 1424 KB Output is partially correct
4 Partially correct 364 ms 3928 KB Output is partially correct
5 Partially correct 343 ms 3940 KB Output is partially correct
6 Partially correct 366 ms 4004 KB Output is partially correct
7 Partially correct 371 ms 5288 KB Output is partially correct
8 Partially correct 357 ms 4020 KB Output is partially correct
9 Partially correct 390 ms 4304 KB Output is partially correct
10 Partially correct 332 ms 4980 KB Output is partially correct
11 Partially correct 344 ms 3876 KB Output is partially correct
12 Partially correct 47 ms 2928 KB Output is partially correct
13 Partially correct 205 ms 4056 KB Output is partially correct
14 Partially correct 243 ms 3956 KB Output is partially correct
15 Partially correct 12 ms 1560 KB Output is partially correct
16 Partially correct 381 ms 4372 KB Output is partially correct
17 Partially correct 309 ms 4444 KB Output is partially correct
18 Partially correct 437 ms 4952 KB Output is partially correct
19 Partially correct 389 ms 4960 KB Output is partially correct
20 Partially correct 206 ms 4472 KB Output is partially correct
21 Partially correct 368 ms 5004 KB Output is partially correct
22 Partially correct 330 ms 3536 KB Output is partially correct
23 Partially correct 332 ms 3536 KB Output is partially correct
24 Partially correct 350 ms 3428 KB Output is partially correct
25 Partially correct 287 ms 3496 KB Output is partially correct
26 Partially correct 350 ms 3464 KB Output is partially correct
27 Partially correct 312 ms 3456 KB Output is partially correct
28 Partially correct 300 ms 3360 KB Output is partially correct
29 Partially correct 349 ms 3376 KB Output is partially correct
30 Partially correct 312 ms 3660 KB Output is partially correct
31 Partially correct 363 ms 3476 KB Output is partially correct
32 Partially correct 321 ms 3476 KB Output is partially correct
33 Partially correct 305 ms 3540 KB Output is partially correct
34 Partially correct 328 ms 3448 KB Output is partially correct
35 Partially correct 327 ms 3452 KB Output is partially correct
36 Partially correct 310 ms 3460 KB Output is partially correct
37 Partially correct 385 ms 3348 KB Output is partially correct
38 Partially correct 337 ms 3596 KB Output is partially correct
39 Partially correct 59 ms 2996 KB Output is partially correct
40 Partially correct 496 ms 4700 KB Output is partially correct