Submission #244229

#	Time	Username	Problem	Language	Result	Execution time	Memory
244229		crossing0ver	Highway Tolls (IOI18_highway)	C++17	6 / 100	439 ms	262148 KiB

highway

#include<bits/stdc++.h>
//#define int long long 
#define pb push_back
#define vi vector<int>
#define pii pair<int,int>
#define ll long long 
#define fi first
#define se second
//#define local
#ifndef local
#include "highway.h"
#endif
using namespace std;
const int N = 1e5+5;
int n,m;
vi adj[N];
int sz[N],P[N],bad[N],vis[N],a,b,GraphSize;
map<pii,int> id;
ll dis;
vi WW;
pii mn = {INT_MAX,0},ans;
#ifdef local
int ask(vi v) {
	if (v.size() != m) {
		cout <<"VECTOR SIZE ERROR:404";
		exit(0);
	}
	int ans =0;
	if (v[2] == 0 ) ans += a;
	else ans += b;
	/*for (int i = 0; i < m;i++) {
		if (v[i]== 0) ans += a;
		else ans += b;
	}*/
	return ans;
}
#endif
vector<int> vec,V,U;
int flag;
 
 
int sizeofcomp(int v,int p) {
	int s = 1;
	for (int i : adj[v]) {
		if (i == p || bad[i]) continue;
		s += sizeofcomp(i,v);
	}
	return s;
}
void dfs(int v,int p) {
	int mx_child = 0;
	sz[v] = 0;
	P[v] = p;
	if (flag==1) {
		vec.pb(id[{v,p}]);
	}
	for (int i : adj[v]) {
		if (i == p || bad[i]) continue;
		dfs(i,v);
		mx_child = max(mx_child,sz[i] + 1);
		sz[v] += sz[i] + 1;
	}
	int e = max(mx_child,GraphSize - sz[v] - 1);
	mn = min(mn, {e,v});
}
void find(vector<int>& v,int root) {
	int l = 0, r = v.size() - 1;
	while (l != r) {
		fill(WW.begin(),WW.end(),0);
		int m = (l + r)/2;
		for (int i = l; i <= m;i++) 
			WW[id[{root,v[i]}]] = 1;
		if (ask(WW) == dis) { l = m + 1;}
		else {
		r = m;
		}
	}
	vi g;
	for (int i = l;i < v.size(); i++) {
		g.pb(v[i]);
	}
	v = g;
}
 
void find_k(int v,int p,int depth,int k) {
	if (depth == k) vec.pb(v);
	for (int i : adj[v]) {
		if (bad[i] || i == p) continue;
		find_k(i,v,depth+1,k);
	} 
}
 
 
int findWithParent(vector <int> v) {
	int l = 0, r = v.size() - 1;
	while (l != r) {
		fill(WW.begin(),WW.end(),0);
		int m = (l + r)/2;
		for (int i = l; i <= m; i++) {
			WW[id[{v[i],P[v[i]]}]] = 1;
		}
		if (ask(WW) == dis) {
			l = m + 1;
		}
		else r = m;
	}
	return v[r];
}
void process(int root) {
	GraphSize = sizeofcomp(root,-1);
	if (GraphSize == 2) {
		ans.fi = root;
		ans.se = adj[root][0];
		return;
	}
	flag = 0;
	vi e;
	fill(WW.begin(),WW.end(),0);
	for (int i : adj[root]) {
		if (bad[i]) continue;
		WW[id[{root,i}]] = 1;
		e.pb(i);
	}
	ll d = ask(WW);
	if (d > dis + b - a) {
		 find(e,root);
		 int x = e[0];
		swap(e[0],e.back());
		e.pop_back();
		find(e,root);
		int y = e[0];
		e.clear();
		adj[root].clear();
		adj[root].pb(x);
		adj[root].pb(y);
		
		vec.clear();
		flag = 1;
		dfs(x,root);
		fill(WW.begin(),WW.end(),0);
		for (int i : vec) WW[i] = 1;
		ll d = ask(WW);
		int D = (d - dis)/(b-a);
		vec.clear();
		find_k(x,root,1,D);
		x = findWithParent(vec);
		D = dis/a - D;
		if (D == 0) {
			while(true) {
				
			}
		}
		vec.clear();
		find_k(y,root,1,D);
		y = findWithParent(vec);
		ans = {x,y};
		return;
	} 
	else { 
		flag = 1;
		vector<vector<int> > v;
		vec.clear();
		for (int i : e) {
		dfs(i,root);
		v.pb(vec);
		vec.clear();
		}
		flag = 0;
		int l = 0, r = v.size() - 1;
		while (v.size() != 1) {
			int m = v.size()/2;
			fill(WW.begin(),WW.end(),0);
			for (int i = m; i < v.size(); i++) {
				for (int x : v[i]) WW[x] = 1; 
			}
			if (ask(WW) == dis) {
				while(v.size() != m) v.pop_back();
			}
			else {
				vector<vector<int> > g = v;
				v.clear();
				for (int i = m; i < g.size(); i++) v.pb(g[i]);
				g.clear();
			}
		}
		int x = V[v[0][0]]^U[v[0][0]]^root;
		adj[root].clear();
		adj[root].pb(x);
		mn = {INT_MAX,0};
		vec.clear();
		flag = 0;
		GraphSize = sizeofcomp(root,-1);
		dfs(root,-1);
		root = mn.se;
	/*	if (adj[root].size() == 1 && GraphSize == 3)  {
			cout  << adj[2][1];
			
		}*/
		process(root);
	}
}
pii solve(vi U,vi V) {
	GraphSize = n;
	dis = ask(WW);
	sizeofcomp(0,-1);
	dfs(0,-1);
	int root = mn.se;
	process(root);
	return ans;
}
void find_pair(int N1, vi U1, vi V1,int a1,int b1) {
	U = U1; V = V1;
	n = N1,m = U.size(),a = a1,b = b1;
	WW.resize(m);
	for (int i = 0; i < m; i++) {
		adj[U[i]].pb(V[i]);
		adj[V[i]].pb(U[i]);
		id[{U[i],V[i]}] = id[{V[i],U[i]}] = i;
	}
	auto x = solve(U,V);
	//return ans;
	#ifndef local
  answer(ans.fi,ans.se);
  #endif
}
#ifdef local
main() {
	int n = 4;
	vi U,V;
	U.pb(0);
	U.pb(0);
	V.pb(1);
	V.pb(2);
	U.pb(2);
	V.pb(3);
	int a = 1, b = 2;
	auto x = find_pair(n,U,V,a,b);
	cout << x.fi <<' '<<x.se ;
}
#endif

Compilation message (stderr)

highway.cpp: In function 'void find(std::vector<int>&, int)':
highway.cpp:79:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = l;i < v.size(); i++) {
                 ~~^~~~~~~~~~
highway.cpp: In function 'void process(int)':
highway.cpp:173:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = m; i < v.size(); i++) {
                    ~~^~~~~~~~~~
highway.cpp:177:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(v.size() != m) v.pop_back();
           ~~~~~~~~~^~~~
highway.cpp:182:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = m; i < g.size(); i++) v.pb(g[i]);
                     ~~^~~~~~~~~~
highway.cpp:169:7: warning: unused variable 'l' [-Wunused-variable]
   int l = 0, r = v.size() - 1;
       ^
highway.cpp:169:14: warning: unused variable 'r' [-Wunused-variable]
   int l = 0, r = v.size() - 1;
              ^
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:220:7: warning: variable 'x' set but not used [-Wunused-but-set-variable]
  auto x = solve(U,V);
       ^

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