oj.uz

Submission #433964

# Submission time Handle Problem Language Result Execution time Memory
433964 2021-06-20T12:48:41 Z AugustinasJucas Highway Tolls (IOI18_highway) C++14
51 / 100
 300 ms 262148 KB 
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
const int dydis = 1e5 + 10;
vector<pair<int, int> > gr[dydis];
int n, m;
long long light, heavy;
int tevas[dydis];
int dist[dydis];
int virs[dydis];
vector<pair<int, int> > brn;
int getLen(){
	vector<int> st;
	for(int i = 0; i < m; i++) st.push_back(0);
	return 1ll * ask(st) / light;
}
void dfs(int v, int came = -1, int dst = 0){
	dist[v] = dst;
	if(came == -1) virs[v] = -1;
	for(auto x : gr[v]){
		if(x.first == came) continue;
		tevas[x.first] = v;
		virs[x.first] = x.second;
		dfs(x.first, v, dst+1);
	}
}
vector<pair<int, int> > getInds(int v, int len){ // first - brianos indeksas, sec - virsunes
	dfs(v, -1);
	vector<pair<int, int> > ret;
	for(int i = 0; i < n; i++){
		if(dist[i] != len) continue;
		ret.push_back({virs[i], i});
	}
	return ret;
}
pair<int, int> solveWhenHave(int v, int len){
	vector<pair<int, int> > inds = getInds(v, len); // cia turetu visi buti blogi, isskyrus viena!
	int l = 0; int r = inds.size()-1; int mid = -1; int kair = inds.size()-1;
	vector<int> askk(m, 0);
	long long turi = len * light;
	while(l <= r){
		mid = (l + r) / 2;
		for(int i = 0; i <= mid; i++) askk[inds[i].first] = 1;
		if(ask(askk) != turi){
			r = mid-1;
			kair = min(kair, mid);
		}else{
			l = mid+1;
		}
		for(int i = 0; i <= mid; i++) askk[inds[i].first] = 0;
	}
	return {v, inds[kair].second};
}
/*
int findOne(int len){ //randa viena node'a
	vector<pair<int, int> > inds;
	for(int i = 0; i < (int) brn.size(); i++) inds.push_back({i, brn[i].first});
	int l = 0; int r = inds.size()-1; int mid = -1; int kair = inds.size()-1;
	vector<int> askk(m, 0);
	long long turi = len * light;
	while(l <= r){
		mid = (l + r) / 2;
		for(int i = 0; i <= mid; i++) askk[inds[i].first] = 1;
		if(ask(askk) != turi){
			r = mid-1;
			kair = min(kair, mid);
		}else{
			l = mid+1;
		}
		for(int i = 0; i <= mid; i++) askk[inds[i].first] = 0;
	}
	return inds[kair].second;
}*/

int findAukste(vector<pair<int, int> > briaunos, int len){
	int l = 0; int r = briaunos.size()-1; int mid;
	vector<int> st(m, 0);
	long long turi = 1ll * len * light;
	int desn = r;
	//cout << "briaunos: \n"; for(auto x : briaunos) cout << "briauna " << x.first << ", jos galas " << x.second << endl; cout << endl;
	 
	while(l <= r){
		mid = (l + r) / 2;
		for(int i = 0; i <= mid; i++) st[briaunos[i].first] = 1;
		if(ask(st) != turi){
			r = mid-1;
			desn = min(desn, mid);
		}else{
			l = mid+1;
		}
		for(auto & x : st) x = 0;
	}
	return briaunos[desn].second;
}

vector<pair<int, int> > aukstai[dydis];
int findFarthest(int v, int len){
	
	dfs(v, -1);
	int mx = 0;
	for(int i = 0; i < n; i++){
		aukstai[dist[i]].push_back({virs[i], i});
		mx = max(mx, dist[i]);
	}
	int l = 1, r = mx, mid;
	long long turi = 1ll * len  * heavy;
	vector<int> st(m, 0);
	int ans = 0;
	while(l <= r){
		mid = (l + r) / 2;
		for(int i = 1; i <= mid; i++){
			for(auto x : aukstai[i]) st[x.first] = 1;
		}
		if(ask(st) == turi){
			r = mid-1;
		}else{
			ans = max(ans, mid);
			l = mid+1;
		}
		for(auto &x : st) x = 0;
	}
	// galas yra ans aukste
	ans++;
	//cout << "galas yra " << ans << " aukste nuo " << v << endl;
	return findAukste(aukstai[ans], len);
}
pair<int, int> solveEil(int len){
	long long turi = light * len;
	int leftmost = -1;
	int l = 0; int r = n-1; int mid;
	vector<int> st(m, 0);
 	while(l <= r){
		mid = (l + r) / 2;
		for(int i = 0; i <= mid; i++) st[i] = 1;
		if(ask(st) == turi){
			leftmost = max(leftmost, mid);
			l = mid+1;
		}else{
			r = mid-1;
		}
		for(int i = 0; i <= mid; i++) st[i] = 0;
	}
	//cout << "leftmost = " << leftmost << endl;
	int raitmost = n-1;
	l = 0; r = n-1;
	while(l <= r){
		mid = (l + r) /2;
		for(int i = mid; i <= n-1; i++) st[i] = 1;
		if(ask(st) == turi){
			raitmost = min(raitmost, mid);
			r = mid-1;
		}else{
			l = mid+1;
		}
		for(int i = mid; i <= n-1; i++) st[i] = 0;
	}
	return {leftmost+1, raitmost};
	
}
/*
 6 5
5 7
1 3
0 1    
1 2
2 3
3 4
4 5

*/
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
	n = N;
	m = V.size();
	light = A; heavy = B;
	bool eile = 1;
	for(int i = 0; i < m; i++){
		gr[U[i]].push_back({V[i], i});
		gr[V[i]].push_back({U[i], i});
		brn.push_back({V[i], U[i]});
		if(!(U[i] == i && V[i] == i+1)) eile = 0;
	}
	int len = getLen();
	if(eile){
		auto ret = solveEil(len);
		answer(ret.first, ret.second);
		return ;
	}
	
	int uu = findFarthest(0, len);
	//cout << "galas yra " << uu << endl;
	auto ans = solveWhenHave(uu, len);
	answer(ans.first, ans.second);
	return ;
	
}
/*

12 11 5 7 6 10
0 2
0 3
2 4
2 5
3 6
3 7
4 8
5 9
8 10
8 11
9 1

*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4936 KB Output is correct
2 Correct 5 ms 4936 KB Output is correct
3 Correct 5 ms 4936 KB Output is correct
4 Correct 6 ms 5008 KB Output is correct
5 Correct 5 ms 4936 KB Output is correct
6 Correct 4 ms 4936 KB Output is correct
7 Correct 4 ms 5012 KB Output is correct
8 Correct 4 ms 5000 KB Output is correct
9 Correct 3 ms 5004 KB Output is correct
10 Correct 4 ms 4936 KB Output is correct
11 Correct 4 ms 5004 KB Output is correct
12 Correct 3 ms 5008 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5064 KB Output is correct
2 Correct 20 ms 5932 KB Output is correct
3 Correct 182 ms 13488 KB Output is correct
4 Correct 156 ms 13332 KB Output is correct
5 Correct 142 ms 13340 KB Output is correct
6 Correct 138 ms 13252 KB Output is correct
7 Correct 183 ms 13324 KB Output is correct
8 Correct 171 ms 13312 KB Output is correct
9 Correct 171 ms 13328 KB Output is correct
10 Correct 142 ms 13336 KB Output is correct
11 Correct 162 ms 14372 KB Output is correct
12 Correct 204 ms 15316 KB Output is correct
13 Correct 196 ms 14640 KB Output is correct
14 Correct 157 ms 14576 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 5580 KB Output is correct
2 Correct 35 ms 6288 KB Output is correct
3 Correct 34 ms 6772 KB Output is correct
4 Correct 111 ms 10664 KB Output is correct
5 Correct 108 ms 10672 KB Output is correct
6 Correct 145 ms 10712 KB Output is correct
7 Correct 116 ms 10728 KB Output is correct
8 Correct 146 ms 10664 KB Output is correct
9 Correct 186 ms 10676 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5064 KB Output is correct
2 Correct 18 ms 5928 KB Output is correct
3 Correct 95 ms 11368 KB Output is correct
4 Correct 187 ms 13272 KB Output is correct
5 Correct 161 ms 13368 KB Output is correct
6 Correct 190 ms 13384 KB Output is correct
7 Correct 176 ms 13316 KB Output is correct
8 Correct 174 ms 13336 KB Output is correct
9 Correct 178 ms 13284 KB Output is correct
10 Correct 177 ms 13324 KB Output is correct
11 Correct 204 ms 14260 KB Output is correct
12 Correct 176 ms 15208 KB Output is correct
13 Correct 226 ms 14712 KB Output is correct
14 Correct 197 ms 15248 KB Output is correct
15 Correct 130 ms 13292 KB Output is correct
16 Correct 170 ms 13264 KB Output is correct
17 Correct 169 ms 14808 KB Output is correct
18 Correct 213 ms 14952 KB Output is correct
19 Correct 138 ms 13340 KB Output is correct
20 Correct 159 ms 15696 KB Output is correct
21 Correct 156 ms 14132 KB Output is correct
22 Correct 183 ms 14136 KB Output is correct
23 Correct 166 ms 13768 KB Output is correct
24 Correct 195 ms 14732 KB Output is correct
25 Correct 221 ms 19264 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 300 ms 262148 KB Execution killed with signal 9
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
2 Halted 0 ms 0 KB -