Submission #140289

#	Time	Username	Problem	Language	Result	Execution time	Memory
140289		bazsi700	Highway Tolls (IOI18_highway)	C++14	0 / 100	25 ms	3704 KiB

highway

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

#define MOD 1000000007
#define ll long long int
#define vi vector<int>
#define vii vector< vector<int> >
#define PI 3.1415926535897932384626433832795
#define INF 9223372036854775807LL
#define hashA 1257958787
#define hashB 1539500609

vector<vector<pair<int,int> > > graph (91000,vector<pair<int,int> >());
bool excluded[91000];
bool inset[91000];
bool was[91000];
bool hasspec[91000];
int dis[91000];
int siz[91000];
int par[91000];
ll n,spec,dist;

void dfs(int v) {
	was[v] = true;
	siz[v] = 1;
	for(auto ed : graph[v]) {
		if(!was[ed.first] && !excluded[ed.first]) {
			par[ed.first] = ed.second;
			dis[ed.first] = dis[v]+1;
			dfs(ed.first);
			if(hasspec[ed.first]) {
				hasspec[v] = true;
			}
			siz[v]+= siz[ed.first];
		}
	}
	if(spec == v) {
		hasspec[v] = true;
	}
}

void putinset(int v) {
	was[v] = inset[v] = true;
	for(auto ed : graph[v]) {
		if(!was[ed.first] && !excluded[ed.first]) {
			putinset(ed.first);
		}
	}
}

int findset() {
	memset(was,false,sizeof(was));
	memset(inset,false,sizeof(inset));
	int sta;
	int cnt = 0;
	for(int i = 0; i < n; i++) {
		if(!excluded[i]) {
	//		cout << i << " ";
			sta = i;
			cnt++;
		}
	}
	//cout << endl;
	par[sta] = -1;
	dfs(sta);
	int big = sta;
	while(big != -1) {
		//cout << sta << " " << big << endl;
		sta = big;
		big = -1;
		for(auto ed : graph[sta]) {
			if(siz[ed.first] > cnt/2 && !excluded[ed.first]) {
				big = ed.first;
				if(!hasspec[ed.first]) {
					hasspec[ed.first] = true;
				} else {
					hasspec[sta] = false;
				}
				siz[sta] = cnt-siz[ed.first];
				siz[ed.first] = cnt;
				break;
			}
		}
	}
	vector<pair<int,int> > nodes;
	for(auto ed : graph[sta]) {
		if(!excluded[ed.first]) {
			nodes.push_back({siz[ed.first],ed.first});
		}
	}
	sort(nodes.begin(),nodes.end());
	int currsiz = 1;
	inset[sta] = true;
	memset(was,false,sizeof(was));
	was[sta] = true;
	bool isspec = false;
	int did = 0;
	for(auto el : nodes) {
	//	cout << currsiz << " " << cnt/2 << " " << el.first << endl;
		if(abs(cnt/2.0-(currsiz+el.first)) < abs(cnt/2.0-currsiz)+0.001) {
			currsiz+= el.first;
		//	cout << "x";
			putinset(el.second);
			if(hasspec[el.second]) {
				isspec = true;
			}
			did++;
		} else {
			break;
		}
	}
	int newspec = -1;
	if(isspec) {
		int cn = 0;
		for(int i = 0; i < n; i++) {
			if(!excluded[i]) {
				inset[i] = !inset[i];
				if(inset[i]) {
					cn++;
				}
			}
		}
		if(cnt-cn > 1) {
			inset[sta] = true;
		}
	} else if(spec == sta) {
		if(nodes.size()-did == 1) {
			for(int i = 0; i < n; i++) {
				if(!excluded[i]) {
					inset[i] = !inset[i];
				}
			}
			newspec = nodes[nodes.size()-1].second;
		}
	}
	vector<int> toask(n-1,0);
	for(int i = 0; i < n; i++) {
		//cout << excluded[i];
		if(inset[i] && i != spec) {
			if(spec == -1 && i == sta) {
				continue;
			}
		//	cout << "a" << i << " ";
			for(auto ed : graph[i]) {
				toask[ed.second] = 1;
			}
		}
	}
//	cout << spec << " " << sta << " " << inset[0] << " " << inset[1] << " " << inset[2] << " " << inset[3] << endl;
	ll x = ask(toask);
//	cout << cnt;
	if(x > dist) {
		for(int i = 0; i < n; i++) {
			if(!inset[i] && !excluded[i]) {
				excluded[i] = true;
				cnt--;
			}
		}
		spec = sta;
		if(newspec != -1) {
			spec = newspec;
		}
	} else {
		for(int i = 0; i < n; i++) {
			if(inset[i]) {
				excluded[i] = true;
				cnt--;
			}
		}
		cnt++;
		if(spec == -1) {
			spec = sta;
		}
		excluded[sta] = false;
	}
//	cout << "asd" << cnt << endl;
	return cnt;
}

void find_pair(int N, vector<int> u, vector<int> v, int A, int B) {
	n = N;
	for(int i = 0; i < n-1; i++) {
		graph[u[i]].push_back({v[i],i});
		graph[v[i]].push_back({u[i],i});
	}
	vector<int> toask(n-1,0);
	dist = ask(toask);
	spec = -1;
	int run = 0;
	//cout << "a" << endl;
	while(findset() > 1) {run++;}
	//cout << spec;
	memset(was,false,sizeof(was));
	memset(excluded,false,sizeof(excluded));
	dis[spec] = 0;
	dfs(spec);
	vector<int> vec;
	for(int i = 0; i < n; i++) {
		if(dis[i]*A == dist) {
			vec.push_back(i);
		}
	}
	while(vec.size() > 1) {
		vector<int> vec1;
		vector<int> vec2;
		for(int i = 0; i < vec.size(); i++) {
			if(i*2 < vec.size()) {
				vec1.push_back(vec[i]);
			} else {
				vec2.push_back(vec[i]);
			}
		}
		vector<int> toaskk(n-1,0);
		for(int el : vec1) {
			toaskk[par[el]] = 1;
		}
		if(ask(toaskk) == dist) {
			swap(vec,vec2);
		} else {
			swap(vec,vec1);
		}
	}
	answer(spec,vec[0]);
}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:207:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < vec.size(); i++) {
                  ~~^~~~~~~~~~~~
highway.cpp:208:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(i*2 < vec.size()) {
       ~~~~^~~~~~~~~~~~
highway.cpp: In function 'int findset()':
highway.cpp:66:5: warning: 'sta' may be used uninitialized in this function [-Wmaybe-uninitialized]
  dfs(sta);
  ~~~^~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 6
• Subtask 4: 0 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31