oj.uz

Submission #1058153

# Submission time Handle Problem Language Result Execution time Memory
1058153 2024-08-14T08:44:21 Z ReLice Highway Tolls (IOI18_highway) C++17
6 / 100
 95 ms 25620 KB 
#include "highway.h"
#include <bits/stdc++.h>
#define ll long long
#define vll vector<ll>
#define pb push_back
#define pf push_front
#define sz size()
#define bc back()
#define pob pop_back()
#define pof pop_front()
#define fr first
#define sc second
using namespace std;
const ll N=2e5+7;
const ll inf=1e18;
vector<vector<array<ll,2>>> g(N), g2(N);
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
	ll M = V.sz;
	ll s, t, rt;
	ll n = N;
	vll v, u;
	ll i;
	
	for(auto i : V) v.pb(i);
	for(auto i : U) u.pb(i);
	
	vector<int> w(M, 0);
	
	ll x = ask(w);
	
	for(i=0;i<M;i++){
		g[v[i]].pb({u[i], i});
		g[u[i]].pb({v[i], i});
	}
	
	{//getting vertex on the path
		ll l = 0, r = n;
		while(l + 1 < r){
			ll m = (l + r) / 2;
			
			if(r - l > 60000) m = 60000;
			
			w.assign(M, 0);
			
			for(i=n-1;i>=m;i--){
				for(auto [to, r] : g[i]) w[r] = 1;
			}
			
			ll y = ask(w);
			
			if(y == x) r = m;
			else l = m;
		}
		
		rt = l - 1;
	}
	
	vll p(n), d(n);
	vll pr(n), tour;
	vector<vll> dd(n);
	
	auto bfs = [&](ll s){
		for(i=0;i<n;i++){
			dd[i].clear();
			d[i] = inf;
			pr[i] = p[i] = -1;
		}
		
		queue<ll> q;
		q.push(s);
		d[s] = 0;
		
		while(q.size()){
			ll x = q.front();
			q.pop();
			
			dd[d[x]].pb(x);
			
			for(auto [to, r] : g[x]){
				if(d[to] > d[x] + 1){
					d[to] = d[x] + 1 ;
					pr[to] = r;
					p[to] = x;
					q.push(to);
				}
			}
		}
		
		tour.clear();
		for(i=0;i<n;i++){
			for(auto j : dd[i]) tour.pb(j);
		}
	};
	
	vll path;
	auto calc = [&](ll N){
		ll l = 0, r = N;
		while(l + 1 < r){
			ll m = (l + r) / 2;
			
			if(r - l > 60000) m = 30000;
			
			w.assign(M, 1);
			
			for(auto i : path) w[i] =0;
			
			//~ cout<<m<<endl;
			for(i=1;i<m;i++) {
				w[pr[tour[i]]] = 0;
				//~ cout<<v[pr[tour[i]]]<<' '<<u[pr[tour[i]]]<<endl;
			}
			
			ll y = ask(w);
				
			if(x == y) r = m;
			else l = m;
		}
		
		return r - 1;
	};
	
	bfs(rt);
	
	ll k = calc(n);
	s = tour[k];
	
	{
		ll x = s;
		while(x != rt){
			path.pb(pr[x]);
			x = p[x];
		}
	}
	
	t = tour[calc(k - 1)];
	
	answer(s, t);
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9816 KB Output is correct
2 Correct 2 ms 9816 KB Output is correct
3 Correct 2 ms 9816 KB Output is correct
4 Correct 3 ms 9816 KB Output is correct
5 Incorrect 2 ms 9816 KB Output is incorrect: {s, t} is wrong.
6 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9816 KB Output is correct
2 Correct 11 ms 11304 KB Output is correct
3 Correct 95 ms 24264 KB Output is correct
4 Correct 92 ms 24056 KB Output is correct
5 Correct 92 ms 24204 KB Output is correct
6 Correct 88 ms 24276 KB Output is correct
7 Correct 85 ms 24168 KB Output is correct
8 Correct 84 ms 24168 KB Output is correct
9 Correct 77 ms 24144 KB Output is correct
10 Correct 83 ms 24148 KB Output is correct
11 Incorrect 83 ms 24236 KB Output is incorrect: {s, t} is wrong.
12 Halted 0 ms 0 KB -

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 11608 KB Output is correct
2 Correct 16 ms 13144 KB Output is correct
3 Correct 19 ms 14912 KB Output is correct
4 Correct 65 ms 24396 KB Output is correct
5 Correct 62 ms 24760 KB Output is correct
6 Correct 67 ms 25416 KB Output is correct
7 Correct 77 ms 25620 KB Output is correct
8 Correct 67 ms 24748 KB Output is correct
9 Correct 68 ms 25084 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9816 KB Output is correct
2 Correct 11 ms 11604 KB Output is correct
3 Correct 63 ms 21280 KB Output is correct
4 Correct 85 ms 24148 KB Output is correct
5 Incorrect 81 ms 24136 KB Output is incorrect: {s, t} is wrong.
6 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 11348 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 11352 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -