oj.uz

Submission #244230

# Submission time Handle Problem Language Result Execution time Memory
244230 2020-07-03T06:05:48 Z crossing0ver Highway Tolls (IOI18_highway) C++17
51 / 100
 637 ms 262148 KB 
#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) 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) 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});
}

/// nice
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 (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;
	}
	//nice
	
	
	flag = 0;
	vi e;
	fill(WW.begin(),WW.end(),0);
	for (int i : adj[root]) {
		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();
		dfs(y,root);
		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) {
	dis = ask(WW);
	GraphSize = 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,0);
	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

highway.cpp: In function 'void find(std::vector<int>&, int)':
highway.cpp:81: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:179:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = m; i < v.size(); i++) {
                    ~~^~~~~~~~~~
highway.cpp:183:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(v.size() != m) v.pop_back();
           ~~~~~~~~~^~~~
highway.cpp:188: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:175:7: warning: unused variable 'l' [-Wunused-variable]
   int l = 0, r = v.size() - 1;
       ^
highway.cpp:175: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:225:7: warning: variable 'x' set but not used [-Wunused-but-set-variable]
  auto x = solve(U,V);
       ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 6 ms 2688 KB Output is correct
4 Correct 6 ms 2688 KB Output is correct
5 Correct 6 ms 2688 KB Output is correct
6 Correct 6 ms 2688 KB Output is correct
7 Correct 6 ms 2688 KB Output is correct
8 Correct 6 ms 2688 KB Output is correct
9 Correct 6 ms 2688 KB Output is correct
10 Correct 6 ms 2688 KB Output is correct
11 Correct 6 ms 2776 KB Output is correct
12 Correct 6 ms 2688 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3072 KB Output is correct
2 Correct 26 ms 4736 KB Output is correct
3 Correct 441 ms 21840 KB Output is correct
4 Correct 345 ms 21220 KB Output is correct
5 Correct 415 ms 21240 KB Output is correct
6 Correct 472 ms 21216 KB Output is correct
7 Correct 420 ms 21108 KB Output is correct
8 Correct 401 ms 21484 KB Output is correct
9 Correct 348 ms 21388 KB Output is correct
10 Correct 392 ms 21464 KB Output is correct
11 Correct 637 ms 23640 KB Output is correct
12 Correct 603 ms 25196 KB Output is correct
13 Correct 428 ms 24424 KB Output is correct
14 Correct 410 ms 22808 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 6008 KB Output is correct
2 Correct 41 ms 9088 KB Output is correct
3 Correct 59 ms 12276 KB Output is correct
4 Correct 275 ms 30840 KB Output is correct
5 Correct 250 ms 31224 KB Output is correct
6 Correct 225 ms 30948 KB Output is correct
7 Correct 285 ms 31468 KB Output is correct
8 Correct 161 ms 30968 KB Output is correct
9 Correct 234 ms 31588 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2924 KB Output is correct
2 Correct 28 ms 4736 KB Output is correct
3 Correct 347 ms 17388 KB Output is correct
4 Correct 584 ms 21720 KB Output is correct
5 Correct 405 ms 21616 KB Output is correct
6 Correct 418 ms 21608 KB Output is correct
7 Correct 503 ms 21608 KB Output is correct
8 Correct 394 ms 21508 KB Output is correct
9 Correct 364 ms 21092 KB Output is correct
10 Correct 355 ms 21212 KB Output is correct
11 Correct 409 ms 22524 KB Output is correct
12 Correct 380 ms 24680 KB Output is correct
13 Correct 410 ms 23904 KB Output is correct
14 Correct 439 ms 24672 KB Output is correct
15 Correct 442 ms 21732 KB Output is correct
16 Correct 494 ms 21732 KB Output is correct
17 Correct 554 ms 24056 KB Output is correct
18 Correct 457 ms 23752 KB Output is correct
19 Correct 417 ms 21384 KB Output is correct
20 Correct 479 ms 25796 KB Output is correct
21 Correct 416 ms 21872 KB Output is correct
22 Correct 474 ms 21744 KB Output is correct
23 Correct 359 ms 21736 KB Output is correct
24 Correct 407 ms 22524 KB Output is correct
25 Correct 516 ms 29304 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 305 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 257 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -