Submission #577663

#	Time	Username	Problem	Language	Result	Execution time	Memory
577663		lukameladze	Poklon (COCI17_poklon7)	C++17	120 / 120	452 ms	90264 KiB

poklon

# include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pb push_back
#define pii pair <int, int>
const int N = 1e6 + 5;
int n,x[N],y[N],le_[N],ri_[N], sumw[N],lew[N],riw[N],cursz = 0;
string ans;
vector <pii > xx;
int mx,lvl[N],par[N],canadd[N];
vector <int> to_binary(int x) {
	vector <int> v;
	while (x > 0) {
		v.pb(x % 2);
		x /= 2;
	}
	reverse(v.begin(),v.end());
	return v;
}
void updanss(int pw, int val) {
	vector <int> vv = to_binary(val);
	string ss = "";
	for (int i = 0; i < vv.size(); i++) {
		if (vv[i] == 1) ss += "1";
		else ss += "0";
	}
	for (int i = 0; i < pw; i++) {
		ss += "0";
	}
	if (vv.size() + pw > cursz) {
		cursz = vv.size() + pw;
		ans = ss;
	}
	else {
		ans = max(ans, ss);
	}
}
void updans(int pw, int val) {
	vector <int> vv = to_binary(val);
	int sz = log2(val) + 1;
	if (sz != vv.size()) {
		//cout<<val<<" "<<log2(val)<<endl;
		exit(0);
	}
	if (sz + pw < cursz) {
		return ;
	}
	if (sz + pw > cursz) {
		cursz = sz + pw;
		xx.clear();
    }
	xx.pb({pw,val});

}
void dfs(int node) {
	if (node == 1) lvl[node] = 0;
	else
	lvl[node] = lvl[par[node]] + 1;
	if (le_[node]) dfs(le_[node]);
	else {
		int lv = lvl[node] + 1;
		updans(lv,lew[node]);
	}
	if (ri_[node]) dfs(ri_[node]);
	else {
		int lv = lvl[node] + 1;
		updans(lv,riw[node]);
	}
}

signed main() {
	std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n;
	for (int i = 1; i <= n; i++) {
		cin>>x[i]>>y[i];
	}
	for (int i = 1; i <= n; i++) {
		if (x[i] > 0) {
			le_[i] = x[i];
			par[x[i]] = i;
		} else lew[i] = -x[i];
		if (y[i] > 0) {
			ri_[i] = y[i];
			par[y[i]] = i;
		}
		else riw[i] = -y[i];
	}
	dfs(1);
	for (int i = 0; i < xx.size(); i++) {
		updanss(xx[i].f, xx[i].s);
	}
	cout<<ans;
}

Compilation message (stderr)

poklon.cpp: In function 'void updanss(int, int)':
poklon.cpp:24:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |  for (int i = 0; i < vv.size(); i++) {
      |                  ~~^~~~~~~~~~~
poklon.cpp:31:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   31 |  if (vv.size() + pw > cursz) {
      |      ~~~~~~~~~~~~~~~^~~~~~~
poklon.cpp: In function 'void updans(int, int)':
poklon.cpp:42:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |  if (sz != vv.size()) {
      |      ~~~^~~~~~~~~~~~
poklon.cpp: In function 'int main()':
poklon.cpp:90:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |  for (int i = 0; i < xx.size(); i++) {
      |                  ~~^~~~~~~~~~~

• Subtask 1: 120 / 120